题解：P16566 [ICPC 2026 APC] Reflect Sort

DGFLSzfd · 2026-05-21 18:20:50 · 题解

卡了我挺久的，不过是一道值得推荐的思维好题。

思路

操作的本质

看完题目，几乎没什么头绪，于是手动模拟一下样例。

可以发现相邻两个数的差的绝对值不论怎么操作都不会变。

考虑其数学本质：2a_i - a_j 可以拆为 a_i+(a_i-a_j)，其本质是以 a_i 为中心对 a_j 进行对称翻转。

我们定义差分数组 d_i = a_{i+1} - a_i。
容易发现：对前缀操作，相当于把前缀整体翻了个面，导致前缀内部的 d_i 符号全部取反。对于后缀操作，同理。

第一个结论：无论操作多少次，所有差分值的绝对值 |d_i| 永远保持不变，操作仅仅是在改变它们的正负号。

注意：位置不相邻的两数之差的绝对值是会变的，不变的是位置相邻的两数之差。

答案的本质与求解

题目要求最终序列“单调不降”。单调不降的定义就是所有的差分 d_i \ge 0。
既然差分的绝对值永远不变，而最终又必须全是大于等于 0 的数，那么最终序列的差分数组是唯一确定的，必然是 d'_i = |d_i|。那么最终的 a_n 可以表示为：

公式右边的求和部分已经是固定常数了。我们要让 a'_n 最小，等价于要让最终的 a'_1 最小。

那么如何把 a_1 调整得尽可能小（但又必须 \ge 1）呢？

举几个例子：
如果以 a_2 为轴翻转 a_1：a'_1 = 2a_2 - a_1 = a_1 + 2(a_2 - a_1) = a_1 + 2d_1。这说明 a_1 移动了 2d_1 的距离。
如果以 a_3 为轴翻转 a_1：a'_1 = 2a_3 - a_1 = a_1 + 2(a_3 - a_1) = a_1 + 2d_1 + 2d_2。

你会发现，每次把 a_1 翻来翻去，它值的改变，本质上就是加上或减去了 2d_1, 2d_2, \dots 的若干组合。

在数轴上，如果你能往前走 2d_1+2d_2，又能往回走 2d_1，那么你净移动的距离就是 2d_2。
通过反复的往前走往后走，我们可以得到若干个固定的“步长”：2d_1, 2d_2, \dots, 2d_{n-1}。

根据数学常识（裴蜀定理），能用这些步长组合跳出的最小正距离，就是它们的最大公约数（GCD）。
我们令 g = \gcd(2d_1, 2d_2, \dots, 2d_{n-1})。

第二个结论：无论怎么操作，a_1 每次变动的值一定是 g 的整数倍。

最终的 a_1 必须满足：

为什么调整 a_1 不会影响最终单调性？

你肯定担心调整 a_1 的过程（使用前缀操作）可能会把后面的差分变成负数。

实际上并不影响，后面的负数可以逐个调整。