【2022牛客多校-2】G Link with Monotonic Subsequence

题意

构造一个排列，使其 $max(lis(p),lds(p))$ 最小。

思路

排列权值的最小值为 $\lceil \sqrt{n}\rceil$ ，即对于一个长度为n的全排列， $max(lis(p),lds(p))$ 的最小值是 $\lceil \sqrt{n}\rceil$ 的上取整。

证明如下：
记排列中的第 $i$ 个元素为 $a_i$ ，对于排列中的每个元素，我们记一个二元组 $(li{s}_i,ld{s}_i)$ ，其中 $li{s}_i$ 表示以第 i 个数结尾的最长上升子序列长度，$ld{s}_i$ 表示以第 i 个数结尾的最长下降子序列长度。
对于每个排列生成的所有二元组中的任意两个二元组，下标分别记为 $i,j$ 且 $i<j$：
①若 $a_i>a_j$，则 $ld{s}_j\ge ld{s}_i+1$；
②若 $a_i<a_j$，则 $li{s}_j\ge li{s}_i+1$；
③若 $a_i=a_j$，则不可能。（a为排列）
因此，对于某个排列生成的所有二元组，其必定是两两不同的。
因此所有二元组中的最大值至少为 $\lceil \sqrt{n}\rceil$ 。

由上述结论，我们可以将整个序列分为若干组，每组 $\lceil \sqrt{n}\rceil$ 块，将每组内元素倒序输出（ m a x { l d s } ≤ ⌈ n ⌉ max\{lds\}\le ⌈\sqrt{n}⌉ max{lds}≤⌈n ​⌉ ），各组正序输出（ m a x { l i s } ≤ ⌈ n ⌈ n ⌉ ⌉ ≤ ⌈ n ⌉ max\{lis\}\le ⌈\frac{n}{⌈\sqrt{n}⌉}⌉\le ⌈\sqrt{n}⌉ max{lis}≤⌈⌈n ​⌉n​⌉≤⌈n ​⌉ ）即可。

代码

#include 
#include 
#include 
using namespace std;
int T,n;
int main()
{
	for (scanf("%d",&T);T--;)
	{
		scanf("%d",&n);
        int k=sqrt(n),i;
        if (k*k!=n) k++;
        for (i=0;i<=n;i+=k)
            for (int j=min(n,i+k);j>i;--j) printf("%d ",j);
		printf("\n");
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18