用1~N构造一个序列，使max(最长上升子序列,最长下降子序列)最小，并且字典序最小。
最近做的构造题好多，这种1~N的序列大多是sqrt(n)的构造。。
官方题解：
其实这是个挺有趣的题，你需要构造一个 1..N 的排列，使得其最长上升序列的长度和最长下降序列的长度的最大值最小。应该比较容易能够想到这个答案是 sqrt(N) 级别的，这个结论的证明可以参考吴文虎的那本组合数学 p21 。
当然这还没有结束，怎么找字典序最小的那个解呢？先看看完全平方数吧，对于 4 ，我们有 2 1 4 3 ，对于 9 ，我们有 3 2 1 6 5 4
9 8 7 。嗯，完全平方数的规律还是好找的，那么 5 呢？不就是加一个数么，1 3 2 5 4
，如果你觉得这是答案，那你就大错特错了，答案是 1 2 5 4 3 。同样，对于 10 ，答案是 1 2 6 5 4 3 10 9 8 7 。
于是我们就可以构造程序，每次以 ceil(sqrt(N)) 为一组，尽量把大的数安排到后面的组中，同时要注意，一定要分出 ceil(sqrt(N)) 组，能让较小的 1 2 这样的数能够排在前面。
最后，这题并不难，但是做到 1Y 也不容易，这就要克服各种逻辑上的问题，形成良好的思维习惯，对于解题来说也是十分重要的。
1 #include <stdio.h> 2 #include <string.h> 3 #include <math.h> 4 int cas, n; 5 int main(){ 6 scanf("%d", &cas); 7 while (cas--) { 8 scanf("%d", &n); 9 int k = sqrt(n+1e-9); 10 if (k * k == n) { 11 for (int i = 0; i < n; i++) 12 printf("%d%c", i/k*k + k - i%k, i==n-1?'\n':' '); 13 continue; 14 } 15 k++; 16 int d = n % k; 17 if (d == 0) d = k; 18 if ((n-d)/k + 2 <= k) 19 for (int i = 0; i < d; i++) printf("%d%c", i==0?1:d-i+1, i==n-1?'\n':' '); 20 else 21 for (int i = 0; i < d; i++) printf("%d%c", d - i, i==n-1?'\n':' '); 22 for (int i = d; i < n; i++) 23 printf("%d%c", d + (i-d)/k*k - (i-d)%k + k, i==n-1?'\n':' '); 24 } 25 return 0; 26 }