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]一次操作选 i3、j1也就是把 3 那个位置减 1 变成 2把 1 那个位置加 1 变成 2数组变成 [2, 2, 2]答案显然就是 1。如果 a [2, 2, 4]总和是 88 除以 3 不是整数所以无论怎么搬都不可能让三个数相等输出 -1。1.2 输入格式、输出格式和数据范围输入第一行是一个整数 n表示数组长度。第二行是 n 个整数 a[1] 到 a[n]。输出最少操作次数或者 -1。数据范围一般是 n 最大 2×10^5a[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; 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; 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^14int 完全装不下。我第一次写这题的时候习惯性地用了 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 当 n1 时永远是 0avg 就是唯一的元素统计循环里 a[i] avg 不成立ans 保持 0输出 0。所以不必单独特判但你要清楚这不是巧合而是代码逻辑天然覆盖了这种情况。第四个坑是“选两个不同下标”这个条件。如果 n 1只要存在需要减少的位置就必然同时存在需要增加的位置因此总能找到 i ≠ j。如果 n 1答案是 0也不需要任何操作。所以这个限制条件从头到尾都不会影响答案但如果构造证明时忽略了它可能会在 n2 或 n1 的边界数据上产生困惑。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 题你会发现它们骨子里都是同一个模型换了件外套。到那时候刷题不用靠题海战术分数自然就上去了。我个人做这道题时最大的体会是越是看起来“短代码”的题越值得把推导过程写完整。你多花十分钟把证明想透省下的是之后在变体题里反复试错的好几个小时。这道题我建议你现在就打开编辑器亲手敲一遍再用自己构造的几个随机数组验证一下最后把“为什么答案是正差值之和”这句话讲给旁边的朋友听。能讲明白这道题就真正是你的了。
CF 2131C Make it Equal 题解：不变量思维与最少操作次数推导
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]一次操作选 i3、j1也就是把 3 那个位置减 1 变成 2把 1 那个位置加 1 变成 2数组变成 [2, 2, 2]答案显然就是 1。如果 a [2, 2, 4]总和是 88 除以 3 不是整数所以无论怎么搬都不可能让三个数相等输出 -1。1.2 输入格式、输出格式和数据范围输入第一行是一个整数 n表示数组长度。第二行是 n 个整数 a[1] 到 a[n]。输出最少操作次数或者 -1。数据范围一般是 n 最大 2×10^5a[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; 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; 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^14int 完全装不下。我第一次写这题的时候习惯性地用了 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 当 n1 时永远是 0avg 就是唯一的元素统计循环里 a[i] avg 不成立ans 保持 0输出 0。所以不必单独特判但你要清楚这不是巧合而是代码逻辑天然覆盖了这种情况。第四个坑是“选两个不同下标”这个条件。如果 n 1只要存在需要减少的位置就必然同时存在需要增加的位置因此总能找到 i ≠ j。如果 n 1答案是 0也不需要任何操作。所以这个限制条件从头到尾都不会影响答案但如果构造证明时忽略了它可能会在 n2 或 n1 的边界数据上产生困惑。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 题你会发现它们骨子里都是同一个模型换了件外套。到那时候刷题不用靠题海战术分数自然就上去了。我个人做这道题时最大的体会是越是看起来“短代码”的题越值得把推导过程写完整。你多花十分钟把证明想透省下的是之后在变体题里反复试错的好几个小时。这道题我建议你现在就打开编辑器亲手敲一遍再用自己构造的几个随机数组验证一下最后把“为什么答案是正差值之和”这句话讲给旁边的朋友听。能讲明白这道题就真正是你的了。