企业官网建设流程全解析

CF 2131C 这道 Make it Equal，是我最近在 Codeforces 上补题时觉得非常值得拿出来写一篇详细题解的一道题。题目不算难，但它在很短的一道题里把“可行性判断”“下界证明”“构造可达”这三件事全考了一遍，非常典型。如果你正处在刷 CF 的 A/B/C 题阶段，或者你发现自己经常“代码写完了但样例过了、一交就错”，那这道题一定要亲手推一遍。核心思路先剧透一句：数组总和不变，所有数相等意味着每个数必须是平均值；平均值不是整数就无解；有解时，最小操作次数等于所有大于平均值的部分的总和。这行结论背后每一步推导都有意义，下面我展开讲。

1. 先读懂题意：操作的本质是“搬运”而不是“改变”

1.1 题面到底在说什么

题目按 CF 常见的表达方式，可以整理成下面这样：

给定一个长度为 n 的整数数组 a。一次操作可以选择两个不同的下标 i 和 j，执行 a[i] 减 1、a[j] 加 1。问最少需要多少次操作，能让数组中的所有元素都相等。如果无论如何都无法做到，输出 -1。

这里要先破除一个常见的误解：很多新手拿到这种题会以为操作是“把一个数变成另一个数”或者“删除某个数”，但实际上这个操作的本质是把一个单位的数值从一个位置搬到另一个位置。你可以把它想象成倒水：i 杯子少了一单位水，j 杯子多了一单位水，所有杯子的总水量没有变。这个“总量不变”就是整道题的核心突破口。

样例方面，假设 a = [1, 2, 3]，一次操作选 i=3、j=1，也就是把 3 那个位置减 1 变成 2，把 1 那个位置加 1 变成 2，数组变成 [2, 2, 2]，答案显然就是 1。如果 a = [2, 2, 4]，总和是 8，8 除以 3 不是整数，所以无论怎么搬都不可能让三个数相等，输出 -1。

1.2 输入格式、输出格式和数据范围

输入第一行是一个整数 n，表示数组长度。第二行是 n 个整数 a[1] 到 a[n]。输出最少操作次数，或者 -1。数据范围一般是 n 最大 2×10^5，a[i] 最大 10^9 左右，这两个数字决定了你必须用 O(n) 或 O(n log n) 的算法，并且中间计算要开 long long。

为什么数据范围很重要？因为如果看到“数组总和”这个量，n 是 2×10^5、a[i] 是 10^9，那么总和最大能到 2×10^14，明显超过 int 的 2×10^9 左右上限。也就是说，哪怕你的思路完全正确，只要用 int 存总和，就可能在某些测试点直接溢出，后面所有判断都是错的。这个点我在第五节还会专门再强调。

2. 从“不可能”开始：先解决可行性判断

2.1 最终状态是确定的，所以先算出平均值

因为每次操作只是把一个单位的数从某个位置搬到另一个位置，整个数组的总和 sum 是操作过程中永远不变的不变量。如果最终所有数都相等，设这个相等的数是 avg，那么最终总和一定是 n×avg。又因为操作不改变总和，所以必须满足 n×avg = sum，也就是 avg = sum / n。

换句话说，如果这道题有解，最终数组里的每一个数都必须等于总和除以 n 得到的平均值。这个结论非常强：它说明目标状态是唯一的，不存在“多个可能的相等值里选最优”的问题。有了唯一目标，问题就从一个“搜索题”变成了“计算题”。

这里有个容易忽略的细节：avg 必须是整数。题目里的 a[i] 都是整数，每次操作是加 1 和减 1，所以整个操作过程里所有数永远都是整数。如果 sum 不能被 n 整除，那 avg 就是一个带小数位的数，任何整数数组都不可能等于它。这种情况下直接输出 -1，后面的步骤都不用看了。

2.2 整除就一定可行吗？先别急着下结论

很多题解到这里会直接说“如果可以整除，答案就是正差值之和”，但实际推导时最好多问一句：能被整除，是不是一定找得到操作方案？答案是肯定的，但需要给出理由，而不是默认“当然可以”。这个理由会在第四节构造方案时正式给出。

简单想一下：如果 avg 是整数，那么所有大于 avg 的位置“多出来”的总量，和所有小于 avg 的位置“缺少”的总量必然相等。因为它们都等于 sum - n×avg 的某种拆分，而 sum = n×avg 保证了这两部分总是一样多。只要这两部分一样多，我总能通过“从多的地方搬，往少的地方塞”的操作把它们补齐，而且每一步操作都合法。所以“能整除”实际上就是“有解”的充要条件。

3. 答案的下界：为什么不可能比“正差值之和”更少

3.1 从目标状态反推每个位置需要变化多少

想清楚目标值 avg 之后，数组里每个位置都被分成了三类：a[i] 大于 avg、a[i] 等于 avg、a[i] 小于 avg。

对于 a[i] > avg 的位置，它在最终状态必须变成 avg，所以它必须失去 a[i] - avg 个单位。对于 a[i] < avg 的位置，它必须得到 avg - a[i] 个单位。a[i] = avg 的位置不需要任何变化。

我们把所有“必须失去”的量加起来，记为 need_down，把所有“必须得到”的量加起来，记为 need_up。由于总和不变，need_down 一定等于 need_up。这个等式不是巧合，它是 sum = n×avg 的直接推论，所以你也可以用它来检验自己求 avg 的过程有没有写错。

3.2 一次操作最多只能把“缺口”缩小多少

现在关键问题来了：一次操作到底能减少多少“总缺口”？

一次操作会选择一个 a[i] 减 1、一个 a[j] 加 1。如果选中的 i 是“需要减少”的位置、j 是“需要增加”的位置，那么这一次操作让 need_down 减少了 1，同时让 need_up 也减少了 1，总缺口缩小了 1 个单位。

但如果选中的两个位置都在同一边，比如都是大于 avg 的位置，把其中一个减 1、另一个加 1，那么一个位置更接近 avg 了，另一个位置反而更远离 avg 了，总缺口根本没有变小，这种操作对最终目标毫无帮助。所以在最优方案里，我们永远不需要考虑这类无意义的操作。

那么结论就很清晰了：需要减少的总量是 need_down，每次有效操作最多只能让这个量减少 1，因此最少操作次数至少是 need_down。这就是答案的下界。只要证明 need_down 次操作一定能完成，那答案就等于 need_down。

4. 构造方案：证明下界确实可以达到

4.1 用双指针模拟“从多的地方搬到少的地方”

证明下界可以达到，最直接的方式是给出一种构造方法。这里我用双指针来构造，虽然求答案时不需要真的执行，但它能非常直观地证明操作的可行性。

先用两个指针：left 指向当前第一个小于 avg 的位置，right 指向当前第一个大于 avg 的位置。每一轮我们做一次操作：把 a[right] 减 1、a[left] 加 1。然后检查：

• 如果 a[right] 已经等于 avg，就把 right 向右移动，直到再次找到一个大于 avg 的位置；
• 如果 a[left] 已经等于 avg，就把 left 向左移动，直到再次找到一个小于 avg 的位置。

这样每一轮操作都会让 need_down 恰好减少 1，同时让需要增加的位置的缺口也减少 1。因为 need_down = need_up，所以执行 need_down 轮之后，所有大于 avg 的位置都会降到 avg，所有小于 avg 的位置也都会升到 avg。整个过程没有任何一步会“卡住”。

4.2 为什么这个过程不会卡住

有人可能会问：如果 left 和 right 在移动过程中相遇了怎么办？或者说，会不会出现“已经没有大于 avg 的位置了，但 still 有小于 avg 的位置”的情况？

答案是不会。假设还存在一个小于 avg 的位置，却不存在大于 avg 的位置，那么此时数组所有元素都 ≤ avg，且至少有一个严格小于 avg，数组总和必然严格小于 n×avg。但操作不改变总和，初始总和就是 n×avg，矛盾。反过来也一样：只要有大于 avg 的位置，就一定有小于 avg 的位置。所以双指针总能找到一对可操作的位置，直到全部相等。

这个“用矛盾证明存在性”的思路在 CF 里非常常见。很多时候你不需要真的把每一步操作都写出来，只要说明“在下界范围内一定存在一个合法构造”，就可以大胆把下界当作答案输出。

4.3 求答案时其实不需要真的模拟构造

既然已经证明了 need_down 就是答案，那代码里就不需要真的去搬数值。我们只需要扫描一遍数组，把每个 a[i] 和 avg 比较，累加所有大于 avg 的差值，输出累加结果即可。

这里我还是要提醒一句：不要因为“代码太短”就跳过构造证明。Codeforces 的题目里，AC 代码和严谨证明往往是两回事。你现在靠“感觉”猜到了答案是正差值之和，可能这道题 AC 了，但下一道变体题目里同样的“感觉”就会带你走偏。把构造过程亲手推一遍，你才算真正吸收了这道题。

5. 完整代码实现与踩坑记录

5.1 C++ 实现

下面直接给出完整可提交的 C++ 代码，我加了注释方便对照上面推导过程：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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'; return 0; } long long avg = sum / n; long long ans = 0; for (int i = 0; i < n; i++) { if (a[i] > avg) { ans += a[i] - avg; } } cout << ans << '\n'; return 0; }

这段代码的时间复杂度是 O(n)，因为只扫描了两次数组，一次读入、一次统计。空间复杂度是 O(n)，因为需要把数组存下来才能在知道 avg 之后再统计。你可能会问能不能优化成 O(1) 空间，当然可以：先读一遍数组求 sum，再把数组重新读一遍统计答案，但 CF 的输入通常是一次性给的，重新读一遍需要把输入流倒回去，反而麻烦，所以直接存数组是最稳妥的做法。

5.2 几个我实际踩过的坑

先说最容易爆的坑：int 溢出。前面算过，n 取 2×10^5、a[i] 取 10^9 时，sum 最大是 2×10^14，int 完全装不下。我第一次写这题的时候习惯性地用了 int，结果本地样例全过，交上去某个大测试点直接 WA。后来把 a、sum、avg、ans 全改成 long long 才过。这里我的建议是：只要题目数据范围里出现了“10^9 + 2×10^5”这种组合，直接默认所有数值相关变量都用 long long，别心存侥幸。

第二个坑是输入输出速度。虽然这道题 n 只有 2×10^5，不至于因为输入慢而 TLE，但 CF 上很多类似题都有多次测试用例，总输入量会大很多。所以我个人习惯在任何 CF 程序的 main 函数开头都写两行：

ios::sync_with_stdio(false); cin.tie(nullptr);

这两行能明显加快 cin/cout 的速度。代价是不能混用 scanf/printf 和 cin/cout，不过对大多数题来说没什么影响。

第三个坑是 n = 1 的情况。当 n = 1 时，数组本来就只有一个数，它已经“所有元素相等”，答案显然是 0。代码里 sum % n 当 n=1 时永远是 0，avg 就是唯一的元素，统计循环里 a[i] > avg 不成立，ans 保持 0，输出 0。所以不必单独特判，但你要清楚这不是巧合，而是代码逻辑天然覆盖了这种情况。

第四个坑是“选两个不同下标”这个条件。如果 n > 1，只要存在需要减少的位置，就必然同时存在需要增加的位置，因此总能找到 i ≠ j。如果 n = 1，答案是 0，也不需要任何操作。所以这个限制条件从头到尾都不会影响答案，但如果构造证明时忽略了它，可能会在 n=2 或 n=1 的边界数据上产生困惑。

5.3 一些题外话：怎么确认自己真的想明白了

写这类题解时我有个习惯：看完答案后，不看别人的代码，先自己把“为什么答案是正差值之和”的推导过程完整写一遍。如果我能用三句话以内让另一个人听明白，说明我是真懂了；如果写着写着发现自己在“背结论”，那大概率下次题目换个皮就认不出来了。

比如这道题，你可以试着给朋友这样讲：因为操作就是搬数值，所以总和不变；目标值只能是平均值，所以先判整除；每个大于平均值的位置都必须把多出来的部分搬走，而一次操作只能搬 1 个单位，所以答案就是多出来部分的总和。这三句话能讲顺，这题你就彻底拿下了。

6. 从这题延伸开：一类“先找不变量，再证下界”的套路

6.1 这类题目的共同特征

CF 里有一大类题，表面是在问“最少操作次数”，但实际考的是“操作过程中什么量不变”。一旦你找到不变量，目标状态通常就被唯一确定了，然后你只需要回答两个问题：第一，最终状态是什么；第二，一次操作最多能让状态离目标近多少。

这道题里不变量是总和，最终状态是全部等于平均值，一次操作最多让差距缩小 1。类似的题目我可以举几个：比如“每次选两个位置，把其中一个变成另一个的值，问能否把所有数变成相等”，这里的操作虽然不同，但思考路径完全一致，先分析操作对哪些量有影响、对哪些量没影响。还有些题把操作改成“每次选一段区间加 1”，那就要研究差分数组怎么变化。核心还是那个套路：不变量定方向，下界定答案，构造证可行。

6.2 我刷题时的思考顺序

我现在拿到一道“最少操作次数”类题目，一般会按这个顺序走：

第一步，把操作翻译成最简单的话。这一步不要跳，即使题面已经说得很清楚，我也会用自己的话复述一遍。比如这道题，“减 1 加 1”本质上就是“搬运”，翻译完思路就打开了一半。

第二步，找不变量。把所有可能不变的量列出来：总和、乘积、奇偶性、最大值最小值、差分数组的和……然后逐个排除。一般来说，题目设计的操作就是为了让某个不变量特别显眼。

第三步，假设到达最终状态，反推每个位置需要变化多少。这一步通常能把答案变成一个求和式子。

第四步，证明下界可达。如果构造不出来，很可能说明下界太乐观了，需要重新考虑。

第五步才是写代码。代码通常是整个流程里最不费脑的部分。

这个顺序可能和很多刚接触竞赛的同学习惯相反，因为新手往往先想“怎么模拟操作”，而不是先想“最终状态长什么样”。但 Codeforces 的题目设计，尤其是 C 题及以后，大部分都是“想清楚结论后代码极短”的结构。你先逼自己从结论出发，慢慢就会发现，这类题的正确率会明显提升。

6.3 为什么说这种训练能让你的 CF 分数更好看

总有人说“codeforces better 就得多做题”，但我觉得准确地说，是多做“能让你建立思维闭环”的题。所谓思维闭环，就是你不仅知道代码怎么写，还能解释为什么这个算法是对的、为什么复杂度能过、为什么边界情况没问题。这道 Make it Equal 就是非常标准的思维闭环训练题：O(n) 的代码，配合 O(1) 的核心结论，考察的却是一个完整的数学推导链。

如果你把这套“找不变量 → 判可行性 → 证下界 → 构造可达 → 写代码”的方法练成本能，再看 CF 的很多 C 题、D 题，你会发现它们骨子里都是同一个模型换了件外套。到那时候刷题不用靠题海战术，分数自然就上去了。

我个人做这道题时最大的体会是：越是看起来“短代码”的题，越值得把推导过程写完整。你多花十分钟把证明想透，省下的是之后在变体题里反复试错的好几个小时。这道题我建议你现在就打开编辑器，亲手敲一遍，再用自己构造的几个随机数组验证一下，最后把“为什么答案是正差值之和”这句话讲给旁边的朋友听。能讲明白，这道题就真正是你的了。