蔚来杯2022牛客暑期多校训练营2 G-Link with Monotonic Subsequence

问题描述

First, let's review some definitions. Feel free to skip this part if you are familiar with them.
A sequence aaa is an increasing (decreasing) subsequence of a sequence bbb if aaa can be obtained from bbb by deletion of several (possibly, zero or all) elements and all elements are in increasing (decreasing) order from the beginning to the end.
A permutation is an array consisting of n distinct integers from 1 to n in arbitrary order. For example,[2,3,1,5,4] is a permutation, but[1,2,2] is not a permutation (222 appears twice in the array) and [1,3,4] is also not a permutation (n=3 but there is 4 in the array).
The problem starts from here.
Link has an array. He is currently learning the longest increasing subsequence algorithm. So he comes up with the following question.
Let the value of a permutation p be max(lis(p),lds(p)), where lis(p) is the length of the longest increasing subsequence of p and lds(p) is the length of the longest decreasing subsequence of p. For all permutations of length n, which one has the minimum value?

输入格式

Each test contains multiple test cases. The first line contains the number of test cases T(1≤T≤1000).

For each test case, there is only one line, containing an integer n(1≤n≤10⁶).

It is guaranteed that the sum of nnn over all test cases does not exceed 10⁶.

输出格式

For each test case, output a single line containing a permutation of length n.

If there are multiple answers, print any of them.

样例输入

3
1
2
3

样例输出

1
1 2
1 3 2

题解

要使最长上升子序列和最长下降子序列的最大值最小，则两者长度应尽量相等，因此上升子序列和下降子序列在序列中应各占一半，即序列应该是一个山峰形状

如：1 3 5 7 9 10 8 6 4 2

 

此时一个序列中只有两个上升（或下降序列），考虑将序列切断，使得整个序列有两个山峰（即四个序列），可以发现最长上升（下降）子序列的长度变短了

 

进一步观察发现上升（下降）序列不一定是连续的，例如上图实际只有一个最长下降子序列（10 9 8 6 4 2）

 

进一步思考，上升和下降其实是相对的，在只考虑上升子序列时，上升子序列的个数会成为下降子序列的长度

 

要使最长上升子序列的长度和最长下降子序列的长度尽可能相等，即只考虑上升子序列时，应使上升子序列的个数和长度尽可能相等，所以最长上升子序列的长度应为序列长度的平方根

 

#include <cstdio>
#include <cmath>
int T,n,m;
int main()
{
    int i,j,k;
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d",&n);
        m=sqrt(n);
        if (m*m<n) m++;
        for (k=1,j=n%m;j<=n;k=j+1,j+=m)
          for (i=j;i>=k;i--)
            printf("%d ",i);
        printf("\n");
    }
    return 0;
}