题解：CF1973C Cat, Fox and Double Maximum

· · 题解

更好的阅读体验。

题意：

给定长度为 n 且 n 为偶数的排列 a，构造出一个排列 b，使得对于序列 c，有 c_i=a_i+b_i 且满足 c_{i-1}<c_i<c_{i+1},i\in(1,n) 的 i​ 的数量最多。

解法：

因为没有连续的两个 c_i 可以满足题目的条件，所以最多存在 \frac n 2 - 1 个 i。

因为 n 属于偶数，所以在 c 中，按照 小的数和大的数 交错构造时（如 3,5,2,4,2），会发现构造出来的数的个数为奇数，那么中间可以而外插入一个小的数（如 3,5,2,[1],4,2）。

这就意味着我们有一次”反悔“的机会。

一种明显的构造方法，先将偶数位作为”大数“分配尽可能大的值，奇数位反之。

容易发现当偶数位存在 1 且奇数位存在 n 时，是无法构造合法方案的。（最大给 1 分配给 n，而 n 最小只能分配到 1，二者相等）

考虑到有一次反悔机会，所以把 1 跳过即可。

然后将选出来将要成为”大数“中越小的数分配越大的值，”小数“中越大的数分配越小的值。

至于为什么这样就是对的，下面是简单的证明。

考虑最坏情况，即”大数“中的数为 2,3,...,\frac n 2，”小数“中的数为 1,\frac n 2 + 1,\frac n 2 + 2,...,n。

此时把”大数“中的 2 加上 n，3 加上 n-1，...，\frac n 2 加上 \frac n 2 + 2。那么”大数“中的数均为 n + 2。

”小数“中的 1 加上 \frac n 2+1，\frac n 2 + 1 加上 \frac n 2，\frac n 2 + 2 加上 \frac n 2 - 1，...。那么”小数“中的数除了第一个数以外均为 n + 1 < n + 2​。

证毕。

code.