1. 这道GESP三级真题到底在考什么每年GESP编程能力等级认证三级考试结束讨论最热烈的往往不是压轴大题反而是某些看似“很简单”的题。这道“分糖果”一本通编号4126原题编号【GESP2506三级】就是典型代表题目讲的是分糖果代码写起来也就二三十行但每年都有不少考生在这上面栽跟头甚至有的同学考完对照答案都还搞不明白自己错在哪。先说题目大意有n盒糖果每盒糖果数量不同小A和小B约定小A可以把自己盒子里多余的糖果分给小B但有一个限制——每次只能从糖果数量最多的那一盒里取糖并且取出的糖只能平均分给除这盒以外的其他所有盒子。小A的目标是在有限次操作之后让糖果数量最少的那一盒的糖果数尽可能多问这个最大值是多少。乍一听很像“小学奥数里的均分问题”实际动手一算会发现里面的弯弯绕不少。这道题挂在“编程启蒙”分类下但它出现在GESP三级卷子里显然不只是考察“读题”和“写循环”这么简单。我平时带学生刷信息学奥赛题目GESP三级的定位是“初步掌握算法设计能力”重点考察的内容包括枚举、模拟、简单贪心、基础排序、二分思想等。这道分糖果题表面上是模拟真正高效的解法却是“贪心二分答案”一步到位考察了好几个核心知识点算是一道性价比非常高的题目——题面短、思路不难、但对你算法思维的扎实程度要求不低。这篇文章我就以这道题为线索完整拆解一下正确的贪心结论怎么来、代码怎么写才不容易错、哪些边界条件最坑人以及如果你是准备GESP三级或者刚开始信息学奥赛入门这道题能给你带来哪些可复用的思维方法。2. 直观思路为什么会超时从模拟到贪心的关键转折第一次看到“分糖果”这道题绝大多数人的反应是直接按题意模拟操作过程每次找出最大值那盒把多余的糖果均分给其他盒子重复执行直到无法继续或者达到目标值。理论上这确实是“最忠实于题目描述”的做法但它有两个致命问题。2.1 模拟操作的“无底洞”在哪里先看一个具体例子。假设有三盒糖果数量分别是1、2、100。按照题目规则第一次操作时糖最多的是第三盒100颗。如果从这盒里取出糖果均分给另外两盒能取出多少这里先留个悬念——题目其实对“取出多少”有隐含约束但哪怕是每次只取一部分出来分操作次数也会非常惊人。如果n比较大、糖果总数比较大模拟操作循环的次数可能高达百万、千万甚至更多三重循环一叠加稳稳超时。这是很多初学者容易忽略的一点。信息学奥赛不是“不管你跑多久只要结果对就行”而是必须在限定时间通常是1秒内跑完所有测试点。三级考试虽然没有四、五级那么严苛但时间复杂度的概念从这一级开始就必须建立。2.2 从“模拟过程”转向“验证答案”既然不能一步步模拟就要换思路。请注意题目问的是一个“最大值”——让最少的那盒尽可能多。这种“求最大/最小值的极值问题”在算法竞赛里有一个非常经典的套路不直接去构造操作过程而是二分答案然后验证某个答案是否可行。用人话说就是我不去模拟整个分糖果的过程而是先猜一个最终的“最少盒糖果数”然后判断按照规则能不能通过若干次操作让每一盒的糖果数都不少于这个数如果能说明这个目标还不够高可以再往上猜如果不能说明目标太高了得往下调整。这种“猜答案验证可行性”的思路正是二分答案的核心思想也是这道题真正想考察的东西。从“模拟整个过程”到“二分验证答案”这个思维转变就是这道题最关键的分水岭。跨过去了代码自然水到渠成跨不过去就容易陷在模拟的泥潭里出不来。2.3 为什么这里的单调性成立二分答案能够使用的前提是答案具有单调性如果目标值x可行那么比x小的目标值一定也可行如果x不可行那么比x大的目标值一定也不可行。对于分糖果这道题单调性非常直观——目标值设得越低每盒要达到这个数就越容易目标值设得越高操作起来就越难。从“每个盒子至少有0颗糖”到“每个盒子至少有1亿颗糖”可行性从“一定可以”逐渐过渡到“大概率不行”中间一定存在一个分界点这个分界点就是我们要求的最大值。正是因为有这个单调性我们才可以用二分法高效逼近答案。如果题目改成分糖果时要满足什么非单调的奇怪条件那这个解法就废了这也是为什么不少题目虽然长得像二分实际却不能用二分的原因——因此做题时一定要先确认单调性再动手。3. 正确解法推导从数学规律到代码落地前面说了大方向这一节我们把细节彻底讲透。3.1 关键结论只有“最大堆的存量”能用来补差题目里那句“从小A的糖果盒中取出多余的糖果分给小B的盒子”其实暗示了一个非常重要的规则细节每次操作取糖的来源是当前糖果数最多的那一盒并且取出的糖要均分给其他所有盒子。很多同学卡在这里如果每次取完原来最多的那盒不再是最多了怎么办如果一次取太多导致某些盒子反而超过了目标值怎么办全纠结在这些过程细节里越想越乱。正确的做法是跳出来看全局。我们不用关心每轮具体是谁在“贡献”糖果只需要关心经过若干次操作后除了最终剩下的那盒“永远最多”的糖果以外其他所有盒子的糖果数是否都能达到目标值x。为什么可以这样看因为每次操作都从当前最多的那盒里取糖而取出来的糖是均分给其他盒子的。在整个过程中我们可以把“给其他盒子补糖”这件事统一理解为从所有盒子中糖果最多的那一盒里不断抽取糖果补给其他不足的盒子。等到其他盒子都补到了目标值x及以上剩下的所有糖果自然都堆在最后那一盒里——反正题目求的是“最少的那盒的糖果数”某一盒特别多完全不影响答案。于是核心问题就变成了一个非常朴素的数学判断设所有盒子的糖果总量为sum想让“其他”n-1盒都至少有x颗糖这些盒子至少需要的总量是 (n-1) * x如果剩下那一盒里原本的糖果数足够支撑这个“补给”就说明x可行。再细化一层。实际操作中不是每一盒都需要补有的盒子原本就比x多有的比x少。只有比x少的盒子需要从“最大堆”那里获得补给。所以更准确的判定是计算所有糖果少于x的盒子距离目标x还差多少把差量全部加起来得到一个总缺口need再看“最大堆”里除了保留x颗之外有多少“富余”可以拿出来补这个缺口。只要富余量大于等于needx就可行。3.2 三步判定法从“需求”到“供给”的核对具体落地时我建议把判定逻辑拆成三步不容易漏、不容易错。第一步找到糖果数最多的那一盒设它的数量为maxCandy。这里有个小陷阱如果通过多次操作原来最多的那盒被分出去了不少糖后来另一盒成了最多的怎么办其实不用慌因为我们判断的是“是否存在可行方案”而每次从当前最多的盒子里取糖最后所有“多余”的糖会集中到某一个盒子里。你可以想象成系统内所有盒子只需要保留x颗其余全部收拢到某个“总仓库”需要补给时从仓库里拨给不够的盒子。只要有仓库里的存量够用就等价于存在一种操作顺序能达成目标。这是这类题里最常用也最重要的“整体思维”。第二步计算所有盒子的总缺口need。遍历所有盒子不包括最终的“仓库”那一盒对所有糖果数小于x的盒子累加 (x - 当前糖果数) 得到need。第三步计算“仓库”的富余量。所谓富余量就是除“仓库”那一盒外其他所有盒子原本超过x的部分也都可以视作“补给来源”……等等这里要特别小心一个逻辑。严格来说因为每一轮取糖都只能从“当前最多”的那一盒取所以真正能够长期充当“补给源”的其实是最初那一盒最大堆。但其他盒子如果本身超过x它并不需要补给也不会主动贡献出去。所以判定时并不需要把“其他盒子超过x的部分”算进富余量。正确的逻辑是如果总糖果量sum中除“仓库”外的n-1盒要达到x总共至少需要 (n-1) * x 颗糖。如果sum减去这(n-1)盒原有的全部糖果后剩余归“仓库”所有的量依然不少于need那么x就可行。用公式表达就是maxCandy - x need其中need是“这n-1个盒子距目标x的缺口总和”。注意maxCandy是初始最大盒的糖果数因为在操作过程中它的糖果会不断减少但始终是“补给源”直到最后稳定。3.3 举个例子直观验证判定逻辑假设有四盒糖果分别为3, 5, 8, 20n4总糖果sum36。现在判断目标值x6是否可行。先看缺口。当前糖果小于6的盒子3差3、5差1总缺口need314。再看最大堆maxCandy20。如果x6最大堆最多可以贡献20-614颗糖给其他盒子。14 4说明x6可行——把3那盒补到6需要3颗5那盒补到6需要1颗从20那盒里取出4颗均分补过去就够剩下16颗依然在最重的盒子里不影响“最少盒”超过6。再看x8是否可行。缺口3差5、5差3、6等等8那盒正好是8差0所以need538。最大堆能贡献20-812颗。12 8可行。再看x12。缺口3差9、5差7、8差4need97420。最大堆能贡献20-128颗。8 20说明x12不可行。也就是说最终答案应该在8和12之间。这个判定过程本质上就是在回答在保证“仓库”最后也至少有x颗的前提下从仓库拿出去的糖能不能把其他所有盒子都托到x以上。理解了这一点代码其实就一行公式的事。3.4 二分框架怎么搭判定函数ready(x)写好后外层套一个二分即可左边界lo 0最少不可能为负数右边界hi sum再多也不可能超过总糖果数除以n但直接取sum也没问题反正二分很快当lo hi时取mid (lo hi 1) / 2注意是向上取整的二分避免死循环若ready(mid)为真说明还能往更高处试lo mid否则hi mid - 1。最终lo就是答案。向上取整的二分很多人第一次写容易卡住。我建议直接记住凡是求“最大值最小”或“最小值最大”的题目二分更新时建议写成 lo mid 的形式对应的mid取上中位数凡是求“最小值最大”或“最大值最小”的反向则 hi midmid取下中位数。这样写不容易死循环。下面是完整的C参考代码#include bits/stdc.h using namespace std; int n; long long a[100005]; bool check(long long x) { long long need 0; long long maxCandy 0; for (int i 0; i n; i) { maxCandy max(maxCandy, a[i]); if (a[i] x) { need x - a[i]; } } return maxCandy - x need; } int main() { cin n; long long sum 0; for (int i 0; i n; i) { cin a[i]; sum a[i]; } long long lo 0, hi sum; while (lo hi) { long long mid (lo hi 1) / 2; if (check(mid)) lo mid; else hi mid - 1; } cout lo endl; return 0; }这里check函数的return语句其实可以再优化——因为need在x很大时会非常大而maxCandy - x可能是负数所以返回false非常自然。这段代码里我用long long全程兜底避免int溢出问题这是竞赛代码必须养成的习惯。4. 边界条件与常见错误这些坑我见过无数人踩算法思路讲完了但很多同学“思路懂了代码还是错”原因几乎都出在边界条件的处理上。下面这些坑我带学生集训时反复强调过这里逐一列出来。4.1 数据范围与溢出问题GESP三级真题的数据范围n通常可以达到10^5级别每盒糖果数也可能到10^9级别。那么总糖果数sum最大就是10^14级别远超int的范围。如果代码里用int存sum、need、maxCandy一旦测试数据给满直接溢出变成负数check函数就会出错最后答案全错。这是最没技术含量、但最容易丢分的一类错误。解决办法就一条涉及求和、比较大小的变量全部声明为long long。别嫌丑竞赛里这条习惯能救你无数次。4.2 二分的边界更新有的同学会把二分写成long long mid (lo hi) / 2; if (check(mid)) lo mid; else hi mid;这样写最大的问题是当lo和hi相邻比如lo2, hi3时mid永远等于2如果check(2)为真lo还是2陷入死循环。这也是二分答案题最经典的死循环陷阱。正确的写法应该是long long mid (lo hi 1) / 2; if (check(mid)) lo mid; else hi mid - 1;道理很简单因为你是“求最大值”mid可行时你要把下界往上提lomid所以mid必须取上中位数否则可能出现“永远试不到更高的那个值”的情况。4.3 check函数里的“最大堆”到底取哪个有同学会问随着操作的进行原来最大的那盒可能不再是最大的那check里还拿初始最大值去减x是不是不严谨这里要再解释一遍。我们的check函数判断的并非“模拟某一种操作过程能否成功”而是“在理想调度下所有盒子能否同时达到x”。因为每一轮都从当前最大的盒子里取糖最终所有多余糖果会被聚拢到某一盒这一盒是谁并不重要重要的是它“有足够的糖可以拿来补”。初始最大值盒子的糖果总量减去它最终必须保留的x颗就是整个系统能拿出去补缺口的“总预算”。只要这个总预算不小于所有盒子的总缺口就必然存在一种取糖顺序能让所有盒子都达标。理解这个“总预算”视角你才能真正理解这道题的贪心本质。如果只背代码不理解原理换个题目稍微变一变就不认识了。4.4 单个盒子糖果数特别多或特别少的极端情况比如n1时只有一盒糖果。按照题目的分配逻辑没有其他盒子可分最少的那一盒就是它自己答案就是这盒的糖果数。但我的代码里n1时need0maxCandya[0]check(x)返回a[0]-x 0即x a[0]都可行二分出的答案正好就是a[0]也没问题。再比如某个盒子糖果数是0也没关系把它当成一个需要补很多糖的盒子即可。还有所有盒子糖果数相等的情况比如三盒全是5。目标是5时need0maxCandy-x0可行——所以答案是5符合直觉。4.5 无解情况的处理题目保证了一定存在某种意义上的答案至少每盒可以保留0颗糖所以答案至少是0所以不需要额外判无解。但如果你用二分答案时左边界是0右边界是sum最终一定会收敛到一个数所以这里安全。5. 从一道题到一类题这套思维能迁移到哪里刷题不能只盯着题面本身。这道“分糖果”虽然短小但它背后的方法论能帮你解决不少看起来八竿子打不着的题目。5.1 “最大值最小/最小值最大”类问题信息学奥赛里有一大类题提问方式非常相似“让某某东西的最大值尽可能小”、“让某某东西的最小值尽可能大”。经典的包括“数列分段”、“跳石头”、“进击的奶牛”等。这些题无一例外都可以用二分答案可行性判定来解决。它们共同的思维特征是问的是极值但直接求极值非常困难如果给你一个候选答案验证它是否可行却相对容易。于是我们二分这个候选答案反复验证逼近最终极值。这种“正难则反”的思维是算法竞赛里最常用的策略之一。5.2 贪心思想的嵌入这道题的check函数本身也是一个贪心——我们并不关心具体怎么分只是用“总预算总缺口”这个贪心条件判断可行性。像这种“不关心过程只看总量约束”的思路在很多资源分配类题目中都能看到比如“木棒切割”、“分披萨”、“装水问题”等。做题时遇到“每次操作都有明确规则但过程极长”的题第一反应就应该是能不能跳过过程只看结果是否满足某个条件如果能大概率就是二分答案的套路。5.3 对GESP三级的备考启发从这道题往回看GESP三级真正想考察的能力其实是三个阅读并理解题意能从长题面里抽象出核心数学模型掌握二分答案框架知道什么时候能用、怎么写不出bug代码基本功扎实包括循环、排序、long long使用、边界条件处理。如果你正在准备GESP三级我建议不要眉毛胡子一把抓地刷题先把“二分答案”这个专题学透。把上面说的“数列分段”“跳石头”全部独立做一遍再回来看这道分糖果你会觉得它不过是一只纸老虎。6. 竞赛环境与备考实操GESP三级考生最容易忽略的细节最后聊一点题外话但我觉得对三级考生特别重要。GESP考试用的是标准的OI竞赛环境编程软件通常是Code::Blocks或者Dev-C评测系统对代码的输入输出格式要求极其严格。很多同学平时在本地IDE上跑得好好的一提交就0分原因往往不是算法错而是没有写#include bits/stdc.h或缺少必要的头文件本地编译器自动帮你补全了但评测机不会输入输出没用对多了空格、少了换行、输出了一堆调试信息数组开小了比如题目说最多10^5个盒子有人只开了10005越界后结果乱掉忘记用long long在极端数据下溢出。这些都是我每年带学生参加GESP考试时反复叮嘱的。所以备考阶段强烈建议你从第一道题开始就用标准竞赛模式写代码不开-stdc11之外的花哨特性不依赖本地编译器的特殊行为每次提交前自查数组大小和数据类型。另外说一个很多考生不知道的小技巧GESP考试使用文本比对判题输出的行末空格会导致答案错误。如果你的代码里用cout ans endl完全没问题但如果用cout ans 就等着吃亏吧。统一用\n或endl输出换行别画蛇添足。还有考试时如果遇到这道题类似的“二分答案”题实在不确定二分边界就多调试几组小数据。比如手算出n3、三盒分别是1、2、100的答案再用代码跑一遍。这种小数据自查往往能在关键时刻救你一命。7. 写在最后这道题教给我的三件事每年讲这道“分糖果”我都觉得它是GESP三级里最有教学价值的一题。它没有复杂的算法模板没有繁琐的代码实现但它强迫你完成一次思维上的“跳跃”——从模拟过程到验证答案。我在实际教学里发现能独立想出二分答案解法的学生不是因为他提前背过“二分答案”这个模板而是因为他养成了“遇到复杂过程先想能否跳到结果”的思维习惯。这种思维习惯远比会背几个模板算法值钱。如果你正在准备GESP三级或刚刚开始信息学奥赛之旅刷完这道题之后不妨再找几道同类型题目练手。每道题多问自己一句“如果我不模拟全过程能不能直接判断某个答案行不行”想通了这一句你就已经超越了大多数只会背代码的选手。最后再分享一个实操小技巧做题时养成“先写暴力解法再拿暴力解法验证高效解法”的习惯。分糖果这道题你可以先写一个“每次找最大值模拟操作”的暴力程序再用上面的二分代码跑同一组随机数据两边结果一对比你就能确认自己的贪心判定没有问题。这个“对拍”技巧是信息学竞赛选手中非常通用且高效的debug方式建议从入门阶段就练起来。