E. 美丽数组 – 详细题解

问题重述

给定数组 $a_1, a_2, \dots, a_n$ 和整数 $k$。你可以先任意重排数组，然后进行若干次操作：每次选择一个下标 $i$，令 $a_i := a_i + k$。目标使数组满足 $b_i = b_{n-i+1}$（即成为回文数组）。求最少操作次数，或输出 $-1$ 表示不可能。

核心观察

• 操作只能将某个元素增加 $k$ 的整数倍，不能减少。因此元素的值只能在其模 $k$ 的剩余类中变化（保持 $\bmod k$ 不变）。
• 最终数组必须对称，即对于每对对称位置 $(i, n-i+1)$，最终值必须相等。因此这两个位置上的原始元素必须属于同一个模 $k$ 剩余类，否则无法通过增加 $k$ 的倍数达到相等（因为模 $k$ 不同，加 $k$ 不改变模 $k$）。
• 重排允许我们任意分配元素到最终位置。因此问题转化为：将 $n$ 个元素分配到 $n$ 个位置（形成一个对称的配对方案），使得每对对称位置上的两个元素属于同一剩余类，并且通过增加 $k$ 的倍数使它们相等，总增加次数最小。

按模 $k$ 分组

将数组元素按 $\bmod k$ 的值分组。设 $r = a_i \bmod k$，则所有 $a_i \equiv r \pmod{k}$ 的元素只能与同余的元素配对，因为对称位置上的两个数必须最终相等，而它们模 $k$ 必须相同。

可行性条件

每个组内元素个数必须满足：如果 $n$ 是偶数，则每组元素个数必须为偶数（因为所有元素都必须配对）。如果 $n$ 是奇数，则有一个位置（中心位置）可以单独放置一个元素（自己与自己对称），因此恰好有一组的元素个数为奇数，其余组必须为偶数。若不符合该条件，则不可能，输出 $-1$。

最小操作次数

对于固定的剩余类 $r$，假设该组内有 $m$ 个元素（按值排序后为 $x_1 \le x_2 \le \dots \le x_m$）。我们需要将它们配对，每对 $(x_p, x_q)$ 最终变为同一个值 $v$，且 $v \ge \max(x_p, x_q)$，并且 $v \equiv r \pmod{k}$。由于只能增加（$+k$ 的倍数），最优策略是让两个数都增加到较大的那个数，或者同时增加到某个更大的值。实际上，若两个数分别为 $x$ 和 $y$（$x \le y$），则使它们相等的最小操作次数为 $(y - x)/k$（因为每次增加 $k$，必须使差值被 $k$ 整除，而同一剩余类保证了 $y-x$ 是 $k$ 的倍数）。总操作次数就是所有配对的 $(y-x)/k$ 之和。

为了最小化总操作次数，我们应该就近配对：将排序后的元素相邻两两配对（即 $(x_1,x_2)$, $(x_3,x_4)$, …）。对于偶数个元素，这是最优的（经典贪心：配对排序后相邻元素）。对于奇数个元素（只能出现在 $n$ 为奇数的唯一一组），我们需要从中选出一个元素放在中心位置（不参与配对），其余偶数个元素配对。此时需要决定移除哪个元素使得剩余配对的代价最小。

设组内排序后为 $x_1 \le x_2 \le \dots \le x_m$（$m$ 为奇数）。移除一个元素 $x_i$ 后，剩下 $m-1$ 个元素（偶数），按相邻配对，总代价为：

• 对于 $i$ 左侧（$1..i-1$），若长度为偶数，则配对为 $(x_1,x_2)$, $(x_3,x_4)$, …；若为奇数，则实际配对方式会改变，但可以通过前缀和快速计算。 更简单的方法：预处理前缀配对的代价和以及后缀配对的代价，然后枚举 $i$，计算将 $x_i$ 作为中心时，左边和右边的配对代价之和。

具体地：

• 定义 $pref[i]$：前 $i$ 个元素（$i$ 为偶数）的最小配对代价，即 $pref[0]=0$，$pref[2] = (x_2-x_1)/k$，$pref[4] = pref[2] + (x_4-x_3)/k$，依此类推。
• 定义 $suf[i]$：从第 $i$ 个元素到末尾（$i$ 为奇数？需要对齐）的配对代价。通常我们定义 $suf[i]$ 为从 $i$ 到末尾（共 $m-i+1$ 个元素）的配对代价，但要求其长度偶数。为了方便枚举中心，可以预处理后缀配对数组。

常用技巧：计算所有相邻对的差 $d_j = (x_{j+1} - x_j)/k$（$j=1..m-1$）。当 $m$ 为奇数时，要选出一个元素 $x_i$ 作为中心，那么剩下的元素配对方式为：

• 左侧：$i-1$ 个元素，若 $i-1$ 为偶数，则配对方式为 $(1,2),(3,4),...,(i-2,i-1)$；若为奇数，则配对方式会变成 $(1,2),...,(i-3,i-2)$，然后多出一个 $x_{i-1}$ 需要与右侧配对？实际上，移除 $x_i$ 后，左右两侧的元素个数分别为 $i-1$ 和 $m-i$，这两个数必须均为偶数（因为总数为偶数）。因此 $i-1$ 和 $m-i$ 同奇偶，且和为偶数，所以要么全偶，要么全奇。由于 $m$ 为奇数，$i$ 的奇偶性决定了它们的奇偶性。如果 $i$ 是奇数，则 $i-1$ 和 $m-i$ 均为偶数；如果 $i$ 是偶数，则 $i-1$ 和 $m-i$ 均为奇数。但偶数个元素可以直接相邻配对，而奇数个元素则不可能（因为剩余元素个数为偶数，要求左右均为偶数）。因此实际上，当 $m$ 为奇数时，只有 $i$ 为奇数（即移除奇数位置）才能使左右均为偶数。所以只需枚举 $i=1,3,5,\dots,m$。

此时左侧 $1..i-1$ 有 $i-1$（偶数）个元素，配对代价为 $\sum_{j=1}^{(i-1)/2} (x_{2j} - x_{2j-1})/k$；右侧 $i+1..m$ 有 $m-i$（偶数）个元素，配对代价为 $\sum_{j= (i+1)/2}^{(m-1)/2} (x_{2j+1} - x_{2j})/k$。（注意索引转换）

用前缀和数组 $pref$ 存储：$pref[0]=0$，$pref[2] = d_1$，$pref[4] = d_1+d_3$，...，即 $pref[2t] = \sum_{j=1}^{t} d_{2j-1}$。后缀和 $suf$：$suf[m+1]=0$，$suf[m-1] = d_{m-1}$（如果 $m-1$ 是奇数？需要保证下标）。实际上，为了统一，我们定义 $diff[i] = (x_{i+1} - x_i)/k$（$i=1..m-1$）。对于奇数长度组，中心选在第 $i$ 个元素（$i$ 为奇数），则左配对的 $diff$ 下标为 $1,3,5,...,i-2$，右配对的 $diff$ 下标为 $i+1,i+3,...,m-2$（注意下标奇偶性）。可以通过预处理前缀奇 $diff$ 和、后缀奇 $diff$ 和来实现。

更简洁的实现（代码中给出的方法）是：分别计算前缀配对的累计和以及后缀配对的累计和，然后枚举所有可能的中心位置，取最小值。由于 $n$ 总和不大，可以承受 $O(m)$ 的计算。

总操作次数

将所有组的最小操作次数相加，即得到总操作次数（注意操作次数是 $(y-x)/k$，所以最后累加的是差值除以 $k$ 后的和）。由于代码中累加的是直接的差值（即 $y-x$），最后再除以 $k$ 输出。因此最终答案为 $\text{total} / k$。

特殊情况

• $n=1$：数组只有一个元素，本身就是回文，操作次数为 $0$。
• 所有元素已经满足回文条件（通过重排可以实现），则答案为 $0$。

算法步骤

1. 读入 $n,k$ 和数组 $a$。
2. 对每个 $a_i$，计算 $r = a_i \bmod k$，将 $a_i$ 加入组 $r$。
3. 检查奇偶性条件：
   • 若 $n$ 为偶数，则所有组的大小必须为偶数。
   • 若 $n$ 为奇数，则恰好有一组大小为奇数，其余为偶数。否则输出 $-1$。
4. 对于每个组，将其元素排序。
   • 若大小 $sz$ 为偶数，则相邻配对，累加 $\sum_{j=0}^{sz/2-1} (x_{2j+2} - x_{2j+1})$ 到 $\text{total}$。
   • 若大小为奇数（只可能有一个组），则需要枚举哪个元素作为中心（即对称轴），计算除去该元素后的最小配对代价，取最小值加到 $\text{total}$ 中。
5. 输出 $\text{total} / k$。

时间复杂度

• 分组：$O(n)$。
• 排序每组：总体 $O(n \log n)$，因为所有元素总数为 $n$。
• 配对计算：每组线性扫描，总 $O(n)$。
• 满足约束 $n$ 总和 $\le 2\times 10^5$，可接受。

正确性说明

• 可行性条件由模 $k$ 不变性决定：同组才能配对，且中心位置（若 $n$ 为奇数）允许一个多余元素单独放置。
• 贪心相邻配对在偶数子集中是最优的，因为若将 $x_a$ 与 $x_b$ 配对（$a<b$），中间的 $x_{a+1},...,x_{b-1}$ 必须与其他配对，容易证明交换配对不会使总代价增加。经典结论：将数轴上的点两两配对使总距离最小，就是相邻配对。
• 对于奇数个元素的组，枚举中心位置并取最小配对的代价也是最优的，因为中心元素不参与配对，剩余元素最优配对依然是相邻配对。

因此算法正确。