P1031 这道题在 GESP 五级考生里出镜率相当高同时也是很多人的第一道“贪心题”。它来自 NOIP 2002 提高组但别被“提高组”三个字吓到放今天看更像一道思路题一堆牌、一个平均数、一次从左到右的遍历代码量满打满算不超过 20 行但它能把“贪心”和“净差值”这两个关键概念讲得特别透彻。这篇文章我会完整拆一遍从最容易被忽视的读题细节到为什么“扫一遍”就是最优解再到 C 实现、常见误区、调试方法最后顺带讲两个扩展方向。不管你是备考 GESP 五级还是单纯想弄明白“均分纸牌为什么能这么做”这篇都值得看完。1. 题目到底在考什么从 GESP 五级视角拆题1.1 先复述题目把容易看漏的条件一次说清楚题目大意是有 N 堆纸牌每堆上有若干张现在要通过若干次操作让每堆纸牌数量相等。每次操作允许在某一堆上取若干张牌然后移动到相邻堆也就是只能向左或者向右移动。问最少操作多少次。输入是 N以及每堆牌的数量 a[i]输出一个整数答案。这里有一个大家扫一眼就可能忽略的前提题目保证纸牌总数一定是 N 的倍数。也就是说“最后每堆变成多少张”是一个确定的、唯一的答案就是总和除以 N 得到的平均值。这个条件不是摆设它直接决定了这道题有没有解也决定了所有推导的锚点在哪里。如果总数不是 N 的倍数那根本不存在“平均分配”的可能题目也就无从谈起。另一个很容易被忽略的约束是“只能在相邻堆之间移动”。这个约束是整道题的灵魂。正因为每次只能往左右相邻堆挪牌才导致第一堆多出来的牌只能先经过第二堆没有第二条路可走。很多人在做这道题时觉得难其实是没抓住“相邻”这两个字。从数据范围看N 最大只有 100很小所以这题考察的重点从来不是怎么卡常数、怎么优化时间而是你能不能把“最小操作次数”这个目标转化为一种可计算的逻辑。想通了答案就是一层循环的事想不通很容易往 BFS、搜索、复杂模拟的方向跑偏。1.2 知识点边界这题算“模拟”还是“贪心”从 GESP 五级考纲的知识点划分来看P1031 通常被归入“贪心算法”这一类但它同时带有模拟和前缀和的影子。很多人对它的第一反应是模拟每次找一堆多的往少的堆挪一挪直到全部相等。这个思路本身没错但如果你真的按“逐张移动”去模拟复杂度会变得很不可控而且很容易出错。贪心的视角则完全不同我们不关心每一张牌具体怎么流动只关心某个堆在“不平衡”状态下必须向右邻堆转移多少净数量。每一次这样的转移如果数量不为零就必然对应一次操作。最终答案是所有“必须转移”的次数之和而不是模拟出来的每一次搬牌动作。我更愿意把这题定义成“一道用贪心思想做的推导题”因为代码本质只是维护一个变量没有复杂的排序、搜索、递归。但如果你能把这题的推导过程完整想明白后面做前缀和、差分、环形均分纸牌都会轻松不少。这也是为什么很多老师会把它放在“贪心入门题库”的第一个位置。2. 核心思路为什么“从左到右扫一遍”就是最优解2.1 平均值是一个唯一的锚点假设所有纸牌总数是 sum堆数是 N那么最终每堆数量必然是 avg sum / N。这个问题最妙的地方在于不管中间怎么操作最终状态是固定的所以我们可以把每一堆的当前数量 a[i] 与目标 avg 的差值 d[i] a[i] - avg 作为分析对象。d[i] 为正说明这一堆多出来了d[i] 为负说明这一堆还缺d[i] 为零说明它已经达标。整个问题就变成了怎么通过相邻之间的搬运把这些差值全部归零。换句话说我们不需要关心牌到底长什么样只需要关心“谁多谁少、多多少少多少”。这种把具体元素抽象成差值的过程是很多算法问题里特别常用的第一步。这里还可以做一个生活化的类比。就好比班级里统计身高你想让所有人平均身高都达到某个值每个人的“目标差值”就是他比平均值高了多少或矮了多少。至于具体谁和谁交换座位那是下一步的事先把每个人的“偏差量”算清楚才有后面的规划。2.2 净差值视角把真实移动换算成“待结算量”现在从左往右看第一堆。如果 d[1] 3说明第一堆多了 3 张牌。题目规定第一堆的牌只能往右走也就是必须先到第二堆任何从第一堆出发的牌都绕不开第二堆。这意味着第一堆的 3 张牌无论如何都要经历“第一堆 → 第二堆”的移动这次操作是必须发生的无法和其他操作合并。同样地如果 d[1] -2说明第一堆少了 2 张牌。这 2 张牌也只能从第二堆方向补过来那么“第二堆 → 第一堆”的操作必然发生一次也无法避免。不管从哪个方向看“第一堆与第二堆之间发生一次操作”这件事从第一堆失衡的那一刻起就已经注定了。于是我们可以把第一堆“抹平”第一堆多 3 张就想象成已经把 3 张“结算”到了第二堆第一堆少 2 张就想象成已经向第二堆“借走”了 2 张。然后把第二堆的数量做相应调整再继续看新的第二堆相对目标值差多少。这个过程中始终只有一个变量在起作用当前堆需要向右传递的净差值我习惯叫它 carry也就是“待结算量”。它的含义是前面已经处理完的堆整体上对当前堆产生了多少“额外积累”。carry 不为零就说明当前堆需要和右邻堆发生一次操作才能让两边继续保持平衡。用这个视角我们成功把“移动若干张牌”这样一个连续的物理过程压缩成了一个一次性的数学结算。这也是为什么这题代码可以写得极短——我们根本不需要真的创建队列、维护数组的实时变化只需要维护 carry 这个标量。2.3 贪心正确性论证为什么局部最优就是全局最优很多初学者会问从左到右处理会不会忽略了更优的方案比如第一堆多 3 张第二堆多 2 张第三堆少 5 张你想让第一堆的 3 张直接“穿过”第二堆给到第三堆不同时拉上第二堆的 2 张有可能一次操作就完事。但问题是第一堆的牌只能先经过第二堆它不可能跳过第二堆直达第三堆。所以从第一堆出发的 3 张必然先被移动到第二堆这就已经是一次操作。等第二堆积累了 3 2 5 张后再把这 5 张一起移动到第三堆又产生第二次操作。两次操作总归省不掉。关键就在这里第一堆与第二堆之间是否需要发生一次操作只取决于第一堆是否等于 avg而与其他堆无关。因为它位于最左侧除了第二堆没有第二个交换对象。只要第一堆不是平均数它就必须和第二堆“互动”一次这个互动无法避免也不可能和后续其他堆之间的互动合并。处理完第一堆后第一堆已经等于 avg整个问题的规模变成了 N-1 堆且最左边界变成了原来的第二堆。对新的最左堆继续做同样的推理又会得出“它必须和右邻互动一次”的结论。如此递推下去每一步的“必须操作”累积起来就是全局的最小操作次数。因为在每一步这个操作都是不可跳过的所以贪心选择的局部最优正好等于全局最优。这里有一个很值得背下来的结论答案不是“模拟出来的实际移动次数”而是“从左到右扫描过程中某个累积差值从零变成非零、或者从一个非零值变成另一个非零值的次数”。想清楚这句话这道题的核心就抓住了。3. 完整代码实现与关键细节3.1 先给一个能直接 AC 的版本下面是我常用的写法不修改原数组也不用担心越界问题逻辑和上面讲的“净差值”完全对应。#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin n; vectorint a(n); int sum 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; } int avg sum / n; int ans 0; int carry 0; // 当前位置需要向右传递的净差值 for (int i 0; i n; i) { int cur a[i] - avg carry; // 当前堆折算后的不平衡量 if (cur ! 0) { ans; carry cur; } else { carry 0; } } cout ans \n; return 0; }这段代码的核心只有循环里的三行。cur 表示“当前堆加上之前所有堆传递过来的不平衡量之后还差多少才等于 avg”。如果 cur 不为零说明当前堆必须和右边发生一次操作如果 cur 恰好为零说明前面的积累刚好被当前堆“吸收”干净不需要额外的操作。网上更常见的经典写法是直接改原数组逻辑上等价for (int i 0; i n - 1; i) { if (a[i] ! avg) { ans; a[i 1] a[i] - avg; } }这种写法更直观很多教材里也是这么教的。它的语义是处理到第 i 堆时如果它不等于 avg就把差值全部转移给下一堆同时操作次数加一。.size()或者改用for (int i 0; i 1 n; i)可以规避一部分问题但对初学阶段来说能少想一层边界就少想一层所以我更推荐 carry 版本。3.2 两个细节数据类型与求和范围很多同学看到这题 N 最多 100就觉得 int 一定是够用的。确实在绝大多数测试数据下int 不会溢出。但“求总和”“算平均数”“做前缀累计”这三件事放在一起就会让我形成一种本能的警惕总和会不会超 int中间的累积结果会不会超过 int尤其是一旦你以后去做环形版本、大数据范围版本或者题目稍微改一下数据范围风险立刻变大。我的建议是凡是涉及“求和、平均值、前缀累积”的算法题初期一律先写long long等你把题目数据范围确认清楚之后再决定要不要缩回 int。这不是性能洁癖而是为了把精力放在算法逻辑上而不是浪费在一次可能的溢出 debug 上。GESP 考试的数据一般不大但养成这个习惯对你做洛谷、力扣上更大数据范围的题目只有好处。还有一个容易被忽略的坑当 n 等于 1 时循环只需要跑一次carry 必然等于 0答案输出 0代码天然正确。没有特判需求这也是 carry 版本优雅的地方。3.3 GESP 考试环境下的输入输出习惯有人会问GESP 考试里用 cin/cout 会不会超时说实话这种数据量的题目不会。但ios::sync_with_stdio(false);和cin.tie(nullptr);这两行我还是建议每次都写上。从.C 学习的角度讲这不是为了这题而是为了让你在日后面临更大数据量时不用临时想起“哦我忘了关同步”。另外输出使用\n而不是endl。endl会额外强制刷新输出缓冲区在大量输出时性能影响明显。这题只输出一个数看不出来差距但这个习惯越早固定越好。我经常跟学生说一个选手的代码是否“老练”不是看会不会写复杂语法而是看这些基础细节有没有内化成肌肉记忆。输入输出风格就是第一张名片。4. 新手最容易踩的坑从“会做”到“做对”4.1 误区一真的去模拟每一张牌的移动我第一次带学生做这题时有不少人第一反应是“用 BFS 枚举状态”或“模拟每次搬一张”。方向就错了。题目只问“最少操作次数”不问“具体怎么移动”所以状态空间根本不需要展开。你如果按纸牌一张张流动去模拟N 只有 100 时也许能跑但思维上已经完全绕远而且很容易被“比如一次移动 5 张和移动 3 张到底怎么算”这种问题绊住。记住这道题的操作次数只看“两个相邻堆之间有没有发生一次结算”不看你结算了多少张牌。一次移动 1 张和一次移动 100 张在计数上完全等价。想明白这一点就不会去做逐张枚举的傻事。4.2 误区二把一次移动算成两次操作还有一个常见错误当 a[i] 大于 avg 时 ans当 a[i] 小于 avg 时又 ans。比如第一堆多 3 张、第二堆少 3 张有人会认为“第一堆给出 3 张”和“第二堆接收 3 张”算两次操作。这显然是错误的。题目原文的表述是“在牌堆上取若干张纸牌移动到相邻堆”整句话描述的是同一个动作取牌、移动、落定整体算一次操作。所以只要这一堆和下一堆之间发生了结算无论方向是左向右还是右向左都只增加 1 次计数。你可以想象成邻居之间借东西张三给李四递一本书不管这本书最后放没放上李四的书架递的这个动作从头到尾就是一次。4.3 误区三循环边界处理出错经典写法里如果循环写成for (int i 0; i n; i)然后在循环体里访问a[i 1]当 i 等于 n - 1 时就会越界。虽然很多人的本意是“最后一堆不需要再向右结转”但代码写出来往往漏了这件事。比较稳妥的处理方式有三种一是循环只跑到 n - 2二是数组开大一点比如用vectorint a(n 1)三是用 carry 版本压根不涉及访问下一堆。我倾向于第三种因为它把边界问题从根上消灭了。还有个隐蔽的小坑如果你用vectorint a(n)但循环写成i n - 1当 n 等于 0 时会出现负数循环不过这题 N 至少是 1不影响。但写代码时最好让自己的逻辑不依赖这类“题目保证”之外的位置。4.4 调试技巧随机对拍 手推样例这种思路题最有效的验证方式不是盯着代码看而是自己写一个暴力模拟程序然后随机生成小数据反复对拍。暴力程序怎么写很简单用一个 while 循环每次找一对相邻堆把多的堆的牌移到少的堆直到全部等于 avg记录移动次数。这个暴力程序可能效率不高但它逻辑上绝对正确足以作为验证基准。我的对拍步骤一般是先写暴力程序brute.cpp再写贪心程序greedy.cpp然后写一个生成随机数据的脚本循环跑 1000 组。一旦两组答案不相等就把当前数据打印出来手动推一遍看是贪心思路有问题还是实现写错了。这个流程几乎能抓到所有隐藏 bug而且比自己“瞪眼 debug”快得多。如果你不想写脚本也可以手推几个特殊边界比如所有堆一开始就相等、只有一堆不相等、前一堆缺后一堆多、某堆差值被中间大堆完全吸收等等。这些特殊数据比随机数据更能暴露逻辑漏洞。5. 一道题带出的扩展环形版本与备考思考5.1 如果是环形糖果传递问题的核心变化如果把“一排纸牌”改成“围成一个环”也就是第一堆和最后一堆也能互相移动问题就变成了另一个经典题糖果传递洛谷 P2512 / 环形均分纸牌。这时上面的“从左到右扫一遍”直接失效因为最左和最右同样相邻第一堆不只依赖第二堆这一个出口边界不再成立。环形版本的经典做法是先算出前缀不平衡量。设 d[i] a[i] - avg前缀和 s[i] d[1] d[2] ... d[i]。可以证明环形均分的最少操作次数等于所有 s[i] 和某个“断点值”的距离之和而这个最优断点值就是 s 数组的中位数。具体的推导过程和结论建议你去搜“糖果传递 中位数”来学习这里不展开。我想强调的点是如果 P1031 你只记住了“从左到右扫一遍”这个结论那环形版本照样不会做但你如果理解了“净差值”“前缀不平衡量”这些本质概念环形版本的解法几乎是水到渠成的。这正是一道题带给你的最大价值。5.2 如果要输出具体移动方案题目没有要求输出方案但如果你在复习或者给别人讲题时想把完整过程展示出来该怎么改其实就是在经典写法的基础上把每一次结算的方向和张数打印出来。思路是从左往右处理到第 i 堆时如果 a[i] ! avg算出需要移动的差量 g a[i] - avg。如果 g 大于 0就输出“从 i 堆往 i1 堆移动 g 张”如果 g 小于 0就输出“从 i1 堆往 i 堆移动 -g 张”。然后更新 a[i1] g把 a[i] 置为 avg。继续处理下一堆。注意在实际移动方案中如果 g 是负数表示当前堆缺牌需要从右边“反向借”输出时不要弄反方向。很多人在这一步会搞混“缺了多少”和“往哪个方向补”之间的关系。我的建议是写一个辅助函数统一按“正数表示向右传负数表示向左借”的语义来打印逻辑清晰不容易错。5.3 对 GESP 五级备考的启发P1031 在 GESP 五级里算是“贪心思想 简单模拟”的代表题型。它不会直接考原题但很可能会换一层皮出现比如“均分石头”“均分零食”“分配任务到相邻工作岗位”等等。考的本质始终是你能不能在一个线性结构上从左到右用一个累积量处理“必然发生的结算”。我给五级备考者的建议是做完这道题之后别急着切下一题先合上题解用自己的话把“为什么从左到右扫一遍就是最优”讲出来。能讲清楚的人说明真的理解了贪心中“局部最优就是全局最优”的逻辑链条讲不清楚的人多半只是背下了代码。后者在 GESP 考试里碰到变形题很容易栽跟头。还有一点做完 P1031 之后最好顺手做几个同题库的贪心入门题比如 P1223 排队接水、P1803 区间选点。它们都属于“看起来简单但推导过程非常经典”的题型。放在一起做你会明显感觉到贪心思想的共通之处找到每个当下无法避免的最小步骤然后让后续问题规模减小继续求解。我带学生刷题时总让他们先回答一个问题“第一堆多出来的牌除了经过第二堆还能从哪里走”只要能答出“哪儿都去不了”这题基本就通了。P1031 就是这样一道题——看起来是纸牌移动实际上考的是你能不能识别出“边界处的必然操作”。这个思路一旦打通以后学前缀和、差分甚至环形均分都会有种似曾相识的亲切感。