CF1017C-The Phone Number-分块构造,根号分块,均值不等式

· · 题解

CF1017C - The Phone Number

题意

给出一个正整数 n(1\leq n\leq 10^5)，请构造一个长度为 n 的排列，使得该排列的 最长上升子序列长度 和 最长下降子序列长度 的加和最小。

思路

考虑分块构造排列。

对于每一个块，元素自左到右是严格上升的。

块与块之间，下一个块的最大值小于上一个块的最小值。

也就是说，最长上升子序列长度 = 最大的块长，最长下降子序列长度 = 块的数量。

例如，n=15 时有如下构造：

[13,14,15],\ [9,10,11,12],\ [5,6,7,8],\ [1,2,3,4]

不难发现，最长上升子序列长度（即最大的块长） =4，最长下降子序列长度（块的数量） =4，加和为 8。这种构造是最优的。

如何确定 最大的块长 和 块的数量？

设最大的块长 =len，块的数量 =cnt。

有：

n=len\cdot cnt sum=len+cnt\geq 2\sqrt{len\cdot cnt}=2\sqrt{n}

当 len=cnt=\sqrt{n} 时，不等式取等号，sum 是最小的。

实现

取块的数量为 \lceil \sqrt{n}\ \rceil，最大的块长为 \lceil \sqrt{n}\ \rceil，按照上述方法构造即可。