(Niuke multi School II) G-LINK with monotonic subsequence (construction question)

subject ：

  The sample input ：

3
1
2
3

Sample output ：

1
1 2
1 3 2

The question ： Given a n, Then output a n The whole arrangement p Make it max(lis(p),lds(p)) Minimum .

analysis ：

I found the rule of this problem by typing a table , That is to say For a length of n The whole arrangement , that max(lis(p),lds(p)) The minimum value of is sqrt(n) Take the whole of , This is right for some n I got it by trial , Then we try to construct and find that we can do it first n The number is divided into blocks from small to large , The size of each piece is sqrt(n) Take the whole of , Then we can directly output the numbers in a block continuously , First output the block with large number in the block , For example, the length is 9 The whole arrangement , We export it directly 7,8,9,4,5,6,1,2,3

The skill of this kind of question is to find the rule by typing the table first , Then try to construct according to the law

Here is the code ：

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
const int N=1e6+10;
vector<int>p[N];
int main()
{
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		scanf("%d",&n);
		int t=(int)sqrt(n-1)+1;
		int cnt=1,tt=1;
		p[1].clear();
		for(int i=1;i<=n;i++)
		{
			if(cnt>t) cnt=1,p[++tt].clear();
			cnt++;
			p[tt].push_back(i);
		}
		for(int i=tt;i>=1;i--)
		for(int j=0;j<p[i].size();j++)
			printf("%d ",p[i][j]);
		puts("");
	}
	return 0;
}