C. The Phone Number

주어진 순열에서 LIS, LDS를 추출했을 때

LIS, LDS끼리 모아서 뭉쳐놔도 결과는 달라지지 않는다. 따라서 길이 n인 순열에서

k개의 LIS가 있고 각 LIS의 min, max값이

max(LIS(k)) < min(LIS(k-1)) 이런 형태를 띄고 있는 상태라면

LDS의 길이는 k가 되고 LIS의 길이는 ceil(n/k)가 된다. (LIS, LDS를 반대로 생각해도 똑같다. 순열이 앞뒤로 reverse될 뿐이다)

ex) n==10

7 8 9 10 4 5 6 1 2 3

우리가 구해야 할건 min(k+ceil(m/k))이므로 1<=k<=n을 다 구해보고 최소값일 때

LIS, LDS를 k에 맞춰 저런 형태로 출력하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
typedef long long ll;
 
int n;
int ans[100001];
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    int k = 1e9, t = 0;
    for (int i = 1; i <= n; ++i) {
        ans[i] = i;
        if (i + ceil(double(n) / double(i)) <= k) {
            t = i;
            k = i + ceil(double(n) / double(i));
        }
    }
    for (int i = 0; i < t; ++i)
        reverse(ans + i * n / t + 1, ans + (i + 1)*n / t + 1);
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << " ";
    return 0;
}