Codeforces 2167D题解：前缀和约束与盈余池构造最少步数

Codeforces 2167D 这道题的题名又长又劝退——"Yet Another Array Problem"，看到"Yet Another"就知道出题人没打算在标题上花心思。但这道题我在赛时卡了很久，倒不是因为操作复杂，而是我一直往 DP、数据结构那边想，完全没意识到题目真正考的是一层非常干净的"守恒量"观察。赛后复盘把整个推导链捋顺之后，才发现整道题从无解判定到最少步数，实际上只用到了两个事实：值只能往右走，前缀和只会越来越小。这篇题解我会把从无解条件、最少操作次数下界到构造性可达的完整思路都展开写一遍，最后附上 C++ 和 Python 的实现细节，顺便聊聊用 Python 提交代码时 list 和 array 到底怎么选。

如果刷题时遇到"数组 + 某种搬运操作 + 问能否达到某个目标状态/最小步数"，这题的推导方式可以当模板用。建议看这篇之前先自己花二十分钟想一下，想不出来再看，收获会大很多。

1. 把题意翻译成"搬砖"：为什么值只能往右走，答案立刻清楚一半

1.1 题意与符号约定

先约定一下题面：给定长度为 n 的数组 a（1 ≤ n ≤ 2×10^5，0 ≤ 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 搬到 j（i < 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 = 3，n = 3，avg = 1，完全整除。可你稍微想一下就知道无解——第一个位置是 0，而它最终也要变成 1，问题在于没有任何值能流到第一个位置，因为所有搬运方向都是从左往右的。第一个位置只能出砖，不能进砖。

用上面的前缀约束式验证：k = 1 时，1 × 1 = 1 ≤ P[1] = 0 不成立，所以无解。这就是前缀约束抓出来的反例。

再换个例子：a = [1, 2, 3]，总和 S = 6，n = 3，avg = 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 算法流程

把前面的推导整理成可执行的步骤，整道题的算法非常短：

1. 读入 n 和数组 a，计算总和 sum。
2. 如果 sum % n != 0，输出 -1。
3. 计算 avg = sum / n。
4. 从左到右扫描，pool 初始为 0，ans 初始为 0：
   • 如果 a[i] > avg，ans += a[i] - avg；
   • pool += a[i] - avg；
   • 如果 pool < 0，标记不可行。
5. 输出 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 手算用例

第四组用例特别能说明方向性：看起来位置 4 有 100 很富余，但它帮不了位置 3，因为砖只能从 3 流向 4，不能从 4 流回 3。这就是前缀约束比"总量可整除"更强的根本原因。

4.3 复杂度与数据范围陷阱

时间上只需要一次线性扫描，O(n)。空间上只用了几个 long long 变量，O(1) 额外空间。

数据范围上有个隐蔽的坑：a[i] 最大 1e9，n 最大 2e5，sum 最大能到 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 = 0，avg = 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; vector<long 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 还是 array？

Python 版本同样简单：

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 ≤ 2e5，list 的开销完全在可接受范围内。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 最大 2e14，int直接溢出成负数，导致 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 下界 + 可达性，是构造题的万能两步走

求最小操作次数的题，我最常用的框架是：

1. 证明一个下界：任何合法方案都至少需要 X 次操作。
2. 构造一个方案：刚好用 X 次操作完成任务。

下界往往来自"每个单位必须至少被处理一次"这种朴素计数。本题里，每个盈余砖块至少要离开原位置一次，而一次操作只能让一个砖块离开，所以操作次数 ≥ 盈余砖块数。构造则往往使用贪心或扫描，本题的盈余池就是最简单的贪心——从左到右，把盈余堆在池子里，遇到缺口就补。

如果构造出来的方案次数恰好等于下界，那答案就是这个数。不需要再优化，因为下界已经是最优解的天花板。

6.3 变体延伸：相邻搬运和双向搬运

如果把操作改成只能选相邻位置 i 和 i+1 搬运，问题会变难。此时每个前缀依然只减不增，可行性条件不变，但操作次数不再是盈余总量，因为一块砖从位置 1 搬到位置 n 需要 n-1 次操作，而不是 1 次。此时最少操作次数会变成所有"需要向右净流过的砖块数"按距离加权求和。这类变体适合拿来巩固前缀和思维，但已经不在这道题的范围内。

如果把方向限制去掉，允许双向搬运，那可行性只有一个条件：sum 能被 n 整除。因为砖可以从任何地方搬到任何地方，左边亏空了从右边拿就行，不再有前缀约束。答案依然是盈余总量 T。神奇的是，双向搬运的答案和单向搬运（可行时）的答案是一样的——方向约束影响的是"有没有解"，不影响"最少步数是多少"。

这一点是我觉得这道题最漂亮的地方：你费尽心思证明了方向约束，最后算答案时它却悄悄消失了。但你又不能忽略它，因为忽略它你就会把无解样例判成有解。

6.4 这套方法还能用在哪些场景里

这种"搬运 + 均值/单调性"的模型，在 CF 里还有不少变体，比如数组整体加减、区间反转、相邻交换等。核心思想都一样：操作之前先问自己三个问题，总量守恒吗？哪个量单调？每个单位的代价是 1 还是随距离变化？

我个人的做题习惯是：把纸对折，左边写下所有"操作前后相等的量"，右边写下所有"操作前后单调的量"。再看题目问的是可行性还是最值，选择从哪边入手。这套方法在 2167D 上帮了大忙，后来遇到很多类似的构造题也能快速找到切入点。

最后分享一个赛时教训：这道题我前四十分钟一直在想怎么用堆维护"最高的几个值"来模拟搬运，方向完全错了。等到逼自己把操作画成砖块图，才意识到根本不需要模拟过程。用笔在纸上把"前缀和单调不增"写出来之后，整个题在十分钟内就解完了。有时候慢下来先想一分钟"什么东西不会变"，比急着写模拟快得多。