Codeforces 2167D 这道题的题名又长又劝退——Yet Another Array Problem看到Yet Another就知道出题人没打算在标题上花心思。但这道题我在赛时卡了很久倒不是因为操作复杂而是我一直往 DP、数据结构那边想完全没意识到题目真正考的是一层非常干净的守恒量观察。赛后复盘把整个推导链捋顺之后才发现整道题从无解判定到最少步数实际上只用到了两个事实值只能往右走前缀和只会越来越小。这篇题解我会把从无解条件、最少操作次数下界到构造性可达的完整思路都展开写一遍最后附上 C 和 Python 的实现细节顺便聊聊用 Python 提交代码时 list 和 array 到底怎么选。如果刷题时遇到数组 某种搬运操作 问能否达到某个目标状态/最小步数这题的推导方式可以当模板用。建议看这篇之前先自己花二十分钟想一下想不出来再看收获会大很多。1. 把题意翻译成搬砖为什么值只能往右走答案立刻清楚一半1.1 题意与符号约定先约定一下题面给定长度为 n 的数组 a1 ≤ n ≤ 2×10^50 ≤ a[i] ≤ 10^9。一次操作可以任选两个下标 i j如果 a[i] 0就让 a[i] 减 1、a[j] 加 1。操作次数不限。问能否通过若干次操作让数组所有元素相等如果可以输出最少操作次数否则输出 -1。我在比赛时把这道题在脑子里简化成了另一个模型数组里的每个元素可以看作一个格子每个单位的 1 就是一堆砖块。一次操作做的事情就是拿起某个格子上的一块砖往右扔出去扔到任意一个更靠右的格子上。扔多远都行只要目标下标更大。这个模型有一个立刻能看到的性质砖块总数永远不变。因为一次操作只是把一块砖换个位置总量守恒。记总和为 S如果最后所有元素都等于同一个值那这个值只能是 avg S / n。当然这里有个前提S 必须能被 n 整除否则答案直接是 -1。1.2 前缀和只减不增是关键除了总量守恒还有一个更容易被忽略的性质因为砖只能往右搬所以对任意一个前缀 [1..k]这个前缀里的砖块总数永远不会增加。它只可能减少当前缀里某块砖被搬到 k 右边时或保持不变当前缀内部搬运或者没人搬。换句话说定义前缀和 P[k] a[1] a[2] ... a[k]那么操作过程中 P[k] 是单调不增的。这不是猜的是操作方向直接决定的——从 i 搬到 ji j等于同时做了一件事所有包含 i 但不包含 j 的前缀都减少 1。没有任何操作能让某个前缀和变大。有了这个前缀和单调不增的判断很多答案其实已经藏在里面了。那些一上来就只检查S 能否被 n 整除就开做的解法十个里有八个会挂在后面这个前缀约束上。1.3 目标状态逐项对照如果最终数组每个元素都是 avg那么对于任意前缀 k最终状态的前缀和必然是 k × avg。前面说过原数组的前缀和 P[k] 只能降不能升所以必须满足k × avg ≤ P[k]对所有 1 ≤ k ≤ n 成立。k n 时两边正好相等总量守恒所以这个约束真正起作用的是 k n 的前缀。这个式子非常关键它就是整道题可行性判断的全部。把前缀约束想明白之后你会意识到题目根本没绕弯能不能均分不看总平均值看的是每个前缀是否自带足够的砖块。左边的坑只能左边的砖来填右边哪怕是座砖山也帮不上忙。2. 无解判定不是均值能整除就万事大吉2.1 从前缀约束到盈余池很多第一次做这题的选手包括我会先写一个检查if (sum % n ! 0) 输出 -1。这没错但远远不够。比如 a [0, 1, 2]总和 S 3n 3avg 1完全整除。可你稍微想一下就知道无解——第一个位置是 0而它最终也要变成 1问题在于没有任何值能流到第一个位置因为所有搬运方向都是从左往右的。第一个位置只能出砖不能进砖。用上面的前缀约束式验证k 1 时1 × 1 1 ≤ P[1] 0 不成立所以无解。这就是前缀约束抓出来的反例。再换个例子a [1, 2, 3]总和 S 6n 3avg 2。整除成立但第一个位置初始 1最终也要变成 2砖只能从左边来可左边已经没位置了。前缀约束1 × 2 2 ≤ P[1] 1 不成立无解。这两个例子说明同一件事均值的整除性只是必要条件前缀约束才是充要条件之一。2.2 用盈余池做可行性判断前缀约束在实际代码里可以这么实现从左到右扫描数组维护一个变量 pool它的含义是当前前缀中比最终均值多出来的砖块数。每扫过一个位置 i就执行pool a[i] - avg如果 pool 变成负数说明前 i 个位置的总和已经少于 i × avg也就是左边的砖不够填左边的坑后面的砖再多也搬不回来直接判无解。为什么这个操作等价于前缀约束因为 pool 在扫描到第 i 位时的值恰好是P[i] - i × avg它正是前缀约束式左边的差。pool 全程非负等价于所有前缀约束都被满足。2.3 无解情况全汇总把两种情况合并无解的完整判定条件就是sum % n ! 0均值不是整数或者扫描过程中 pool 出现负值。值得注意的是pool 在最后一个位置一定能回到 0因为总量守恒P[n] n × avg。所以哪怕中途 pool 变负只要把它继续扫完最后一定收敛到 0。但我们已经不需要看它归零了中途有任何一次 pool 0 就可以提前输出 -1。多说一句验证可行性的时候 pool 用的是差值不是绝对值。这是很多人写错的地方——有人会下意识写 pool abs(a[i] - avg)那就完全错了可行性判断必须用带符号的差值。3. 最少操作次数的下界与上界答案就是总盈余3.1 下界每个多余单位必须被搬一次现在假设可行性检查通过了我们要回答第二个问题最少操作次数是多少先找下界。考虑任意一个位置 i如果 a[i] avg说明它一开始就有多余砖。最后这个位置只能留下 avg 块砖所以至少有 a[i] - avg 块砖必须从这个位置被搬出去。关键点来了每次操作最多只能从一个位置搬走一块砖。这个位置视角的下界是显然的——一次操作只让一个源位置的砖数减 1所以所有位置最终都要减到 avg需要搬出的砖块总数就是T Σ max(0, a[i] - avg)这个 T 是任何合法方案的操作次数下界。换句话说操作次数不可能比 T 更少因为每一块必须离开原位置的砖都至少要经历一次操作才能离开。3.2 上界与构造盈余池扫描就是操作方案光有下界还不够万一实际做起来需要中间转手操作次数会超过 T。那就需要构造一个操作数恰好等于 T 的方案。构造方法其实就是前面盈余池的另一种读法从左到右扫描依然维护 pool。当 a[i] avg 时多出的 a[i] - avg 块砖进入 pool这些砖就是待搬走的盈余砖块当 a[i] avg 时当前位置缺 avg - a[i] 块砖直接从 pool 里取出对应数量的盈余砖块搬到这个位置。因为可行性条件保证了 pool 全程非负所以这个贪心过程不会中途卡死。每个盈余砖块恰好被取出一次、搬运一次、到达一个缺口位置。没有哪块砖被搬了两次因为我们的构造里所有缺口位置的补入量正好等于它的缺口量补完就刚好达到 avg不会再有多余的砖需要二次搬出。所以这个构造方案的操作次数恰好等于 T也就是下界。3.3 答案还可以换个角度看由于总量守恒缺口的砖块总数一定等于盈余的砖块总数Σ max(0, avg - a[i]) Σ max(0, a[i] - avg)所以答案 T 同时也等于Σ |a[i] - avg| / 2这个形式和把数组变成全相等的双向最小操作次数一模一样。没错在没有方向限制的版本里答案也是这个。方向限制影响的只是可行性判断——左边亏空就无解不影响盈余总量的计算。这个反直觉的结论恰恰是这道题的灵魂。4. 完整算法、伪代码与三组手算4.1 算法流程把前面的推导整理成可执行的步骤整道题的算法非常短读入 n 和数组 a计算总和 sum。如果 sum % n ! 0输出 -1。计算 avg sum / n。从左到右扫描pool 初始为 0ans 初始为 0如果 a[i] avgans a[i] - avgpool a[i] - avg如果 pool 0标记不可行。输出 ans 或 -1。伪代码read n, array a sum sum(a) if sum % n ! 0: print(-1) return avg sum / n pool 0 ans 0 for i in 1..n: if a[i] avg: ans a[i] - avg pool a[i] - avg if pool 0: ok false print(ok ? ans : -1)这里有个小细节ans 的累加可以放在 pool 更新之前或之后顺序不影响。因为 ans 只统计源位置的盈余量跟 pool 的当前值无关。4.2 手算用例输入sumavg可行性ans说明[2, 0]21可行1把位置 1 的一块砖搬到位置 2得到 [1, 1][0, 1, 2]31无解-1位置 1 是 0无法变成 1前缀约束失败[5, 0, 1]62可行3位置 1 盈余 3分别补位置 2 和位置 3得到 [2, 2, 2][100, 0, 0, 100]20050无解-1位置 3 缺 50但左边盈余不够补到它前缀约束在 k3 失败第四组用例特别能说明方向性看起来位置 4 有 100 很富余但它帮不了位置 3因为砖只能从 3 流向 4不能从 4 流回 3。这就是前缀约束比总量可整除更强的根本原因。4.3 复杂度与数据范围陷阱时间上只需要一次线性扫描O(n)。空间上只用了几个 long long 变量O(1) 额外空间。数据范围上有个隐蔽的坑a[i] 最大 1e9n 最大 2e5sum 最大能到 2e14。这个量级用 int 必炸C 必须用 long long。Python 的 int 无限大没这个问题但 C 选手如果顺手写了 int sum测样例没事一交上去就是 WA 而不是 RE很难排查。我的习惯是看到 1e9 级别元素求和的题直接用 long long 起步不要犹豫。另外一个边界情况是 n 1。此时 avg a[1]T 0不需要任何操作数组已经全部相等输出 0。全 0 数组同理sum 0avg 0扫描全程 pool 0答案 0。5. C 与 Python 提交代码细节与两个隐藏坑5.1 C 完整实现#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin T; while (T--) { int n; cin n; vectorlong long a(n); long long sum 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; } if (sum % n ! 0) { cout -1 \n; continue; } long long avg sum / n; long long pool 0; long long ans 0; bool ok true; for (int i 0; i n; i) { if (a[i] avg) { ans a[i] - avg; } pool a[i] - avg; if (pool 0) { ok false; } } cout (ok ? ans : -1) \n; } return 0; }代码没什么花哨的地方核心就是那三行累加 ans、更新 pool、检查 pool。注意 pool 0 时我们没有 break这是为了避免多组测试数据下输入读取不完整。虽然即便 break 也不影响后续组因为每组数据已经先全部读进 vector 了但没有 break 的写法更省心。5.2 Python 实现用 list 还是 arrayPython 版本同样简单import sys def main(): data list(map(int, sys.stdin.buffer.read().split())) t data[0] idx 1 out [] for _ in range(t): n data[idx] idx 1 a data[idx:idx n] idx n s sum(a) if s % n ! 0: out.append(-1) continue avg s // n pool 0 ans 0 ok True for x in a: if x avg: ans x - avg pool x - avg if pool 0: ok False out.append(str(ans if ok else -1)) sys.stdout.write(\n.join(out)) if __name__ __main__: main()输入用sys.stdin.buffer.read().split()一次性读入再整体转成 int这是在 CF 上 Python 读大数组最快的写法。如果你用 for 循环加input()逐个读 n 个数遇到 2e5 的数据虽然勉强能过但完全没有必要一次 read 搞定。现在说热词里那个很常见的纠结Python 里 array 和 list 到底用哪个结论是这道题用 list。数据量 n ≤ 2e5list 的开销完全在可接受范围内。list 里每个元素是一个 Python int 对象内存占用偏大2e5 个元素大约几 MB在 CF 的 256MB 内存限制下毫无压力。array(q) 是把元素存成连续 C 类型内存更省但构造需要额外转换遍历下标时返回的 Python int 也需要拆包装箱实际跑起来并不比 list 快甚至更慢。只有当数据量到千万级别、内存吃紧时才值得考虑 array。还有一点如果本地测试时遇到类似 maximum array size exceeded 的错误那通常是往 list 里塞了大对象或者开了过大的数组跟本题无关。n 2e5 这个级别list 完全不会爆内存。5.3 两个差点让我翻车的坑第一个坑是用int而不是long long。前面提过 sum 最大 2e14int直接溢出成负数导致 sum % n 判断错误。这个坑在赛场上特别阴因为样例数据小跑出来的结果全对一交大数据就 WA。第二个坑是 Python 里的整除方向。//是向下取整但如果先判断了s % n 0那么s // n得到的就是精确整数不存在负号问题。如果你偷懒不判整除直接avg s // n那遇到负数余数时 avg 会出错。虽然这题元素非负sum 非负不会踩到但很多类似的题数组可能含负数养成先判整除、再取整除的习惯能省去很多麻烦。6. 赛后总结Yet Another Array Problem类题的通法6.1 遇到操作题先找不变量和单调量这类题名字里带 Yet Another十有八九不是考复杂数据结构而是考你能不能从操作里提炼出几个操作中不变或只朝一个方向变化的量。本题的不变量是总和单调量是任意前缀和——只减不增。有了这两个量可行性条件几乎是白送的。以后看到给数组每次操作把某个位置的 1 移到另一个位置这类描述第一反应应该是列一张表什么在操作过程中保持不变什么只朝一个方向变值只能从左往右移动时前缀和的单调性就死死锁住了所有可能结果。6.2 下界 可达性是构造题的万能两步走求最小操作次数的题我最常用的框架是证明一个下界任何合法方案都至少需要 X 次操作。构造一个方案刚好用 X 次操作完成任务。下界往往来自每个单位必须至少被处理一次这种朴素计数。本题里每个盈余砖块至少要离开原位置一次而一次操作只能让一个砖块离开所以操作次数 ≥ 盈余砖块数。构造则往往使用贪心或扫描本题的盈余池就是最简单的贪心——从左到右把盈余堆在池子里遇到缺口就补。如果构造出来的方案次数恰好等于下界那答案就是这个数。不需要再优化因为下界已经是最优解的天花板。6.3 变体延伸相邻搬运和双向搬运如果把操作改成只能选相邻位置 i 和 i1 搬运问题会变难。此时每个前缀依然只减不增可行性条件不变但操作次数不再是盈余总量因为一块砖从位置 1 搬到位置 n 需要 n-1 次操作而不是 1 次。此时最少操作次数会变成所有需要向右净流过的砖块数按距离加权求和。这类变体适合拿来巩固前缀和思维但已经不在这道题的范围内。如果把方向限制去掉允许双向搬运那可行性只有一个条件sum 能被 n 整除。因为砖可以从任何地方搬到任何地方左边亏空了从右边拿就行不再有前缀约束。答案依然是盈余总量 T。神奇的是双向搬运的答案和单向搬运可行时的答案是一样的——方向约束影响的是有没有解不影响最少步数是多少。这一点是我觉得这道题最漂亮的地方你费尽心思证明了方向约束最后算答案时它却悄悄消失了。但你又不能忽略它因为忽略它你就会把无解样例判成有解。6.4 这套方法还能用在哪些场景里这种搬运 均值/单调性的模型在 CF 里还有不少变体比如数组整体加减、区间反转、相邻交换等。核心思想都一样操作之前先问自己三个问题总量守恒吗哪个量单调每个单位的代价是 1 还是随距离变化我个人的做题习惯是把纸对折左边写下所有操作前后相等的量右边写下所有操作前后单调的量。再看题目问的是可行性还是最值选择从哪边入手。这套方法在 2167D 上帮了大忙后来遇到很多类似的构造题也能快速找到切入点。最后分享一个赛时教训这道题我前四十分钟一直在想怎么用堆维护最高的几个值来模拟搬运方向完全错了。等到逼自己把操作画成砖块图才意识到根本不需要模拟过程。用笔在纸上把前缀和单调不增写出来之后整个题在十分钟内就解完了。有时候慢下来先想一分钟什么东西不会变比急着写模拟快得多。