题目翻译

给出 $n(1\leq n\leq 2\times 10^5$，构造一个排列使得 $\operatorname{len(LIS)+len(LDS)}$ 最小。

题目思路

样例提示我们分块操作，设分了 $x$ 块，每块块长为 $\frac{n}{x}$。我们这里为了方便书写先只讨论整除的情况，不整除是一样的。

那么我们就是最小化 $x+\frac{n}{x}$，显然 $x=\sqrt n$ 最优。

那么就很好构造了，参考样例从大到小分组即可。

完整代码

#include <bits/stdc++.h>
using namespace std;
int n;
int main()
{
    cin >> n;
    int m = sqrt(n);
    for (int i = 1; i <= (n + m - 1) / m; i++)
    {
        for (int j = n - i * m + 1; j <= n - (i - 1) * m; j++)
            if (j > 0)
                cout << j << " ";
    }
    cout << endl;
    return 0;
}