【题解】CF2103E Keep the Sum

· · 题解

CF2103E 题解

更差的阅读体验。

不难注意到题目所述操作的本质是：对一对满足 a_i+a_j=k 的 (a_i,a_j)，在和不变，且分配后仍然有 0\le a_i,a_j \le k 的情况下重新进行分配。

比如 a_i=2,a_j=7,k=9 时，一次操作可以让 (a_i,a_j) 变为 (0,9) 或 (1,8) 或 (2,7) 或 (3,6) 等等。

分析题目条件。发现操作次数不多于 3n 且要让数组单调不降。考虑进行 n 次在 3 步之内交换数组中的两个数，使得原数组从小到大排序。

假设要交换 a_x 和 a_y。当 a_x+a_y=k 时，操作是简单的。

考虑 a_x+a_y\neq k 的情况。发现我们必须借助另外一组 a_i+a_j=k 来交换 a_x 和 a_y。

如何借助呢？回顾交换的本质，我们要需要先把 a_x 放到一个临时变量里。对应到这题，我们需要把 a_i 或 a_j 中的一个换成 a_x。之后的操作就变得显然了。

令 px=a_x，py=a_y，pi=a_i，pj=p_j。我们可以按如下方式交换：

操作次数 此时 a_x 此时 a_y 此时 a_i 此时 a_j 操作的 (i,j,k)
初始 px py pi pj 无
第一次操作 px py px k-px (i,j,pi-px)
第二次操作 py py px k-py (x,j,px-py)
第三次操作 py px px k-px (y,j,py-px)

发现此时 a_i+a_j=k 依然成立，因此我们可以多次借助 a_i 和 a_j 进行操作。

但是有一个问题：在我们对其它数排完之后，剩下的 a_i 和 a_j 还没有排序到位。而我们的操作次数已经快要用完了。

怎么办呢？如果这两个数再操作一步就可以使得整个序列有序就好了。于是我们考虑让 a_1 和 a_n 相加等于 k。这样只需一次操作使得 a_1=0,a_n=k 就可以了。

跟交换数一样，我们考虑借助一组 a_i+a_j=k 来让 a_1 和 a_n 相加等于 k。这个比较显然，这里直接给出方案（令 pa = a_1,pb=a_n）：

操作次数 此时 a_1 此时 a_n 此时 a_i 此时 a_j 操作的 (i,j,k)
初始 pa pb pi pj 无
第一次操作 pa pb pb k-pb (i,j,pi-pb)
第二次操作 pa k-pa pb pa (n,j,pa+pb-k)

所以，我们先进行上表所述操作。接着对 2 到 n-1 利用交换进行排序，最后通过操作让 a_1=0,a_n=k（这个很显然了，具体怎么操作留给各位思考）即可。

问题来了：给定一个数组，每次可以交换任意两个数，如何通过不超过 n 次交换进行排序呢？这是个很经典的问题，参考 CF489A 的 O(n) 做法即可。

于是原问题获得顺利的解决。

代码。