（牛客多校二）G-Link with Monotonic Subsequence（构造题）

题目：

 样例输入：

3
1
2
3

样例输出：

1
1 2
1 3 2

题意：给定一个n，然后输出一个n的全排列p使得其max(lis(p),lds(p))最小。

分析：

这种题目我是通过打表发现的规律，就是说对于一个长度为n的全排列，那么max(lis(p),lds(p))的最小值是sqrt(n)的上取整，这是对一些n试探得到的，然后尝试构造发现我们可以先对n个数进行从小到大分块，每块大小为sqrt(n)的上取整，然后我们直接把一个块内的数连续输出即可，先输出块内数字比较大的块，比如长度为9的全排列，我们直接输出7，8，9，4，5，6，1，2，3

这种题的做题技巧就是先打表找一下规律，然后跟着规律尝试去构造

下面是代码：

#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;
}