GESP五级卡了不少人尤其是一到贪心算法这种“一看就懂、一写就错”的模块很多考生直接懵掉。贪心算法在五级考纲里属于高频考点选择题要考编程题更是动不动就拿来当压轴。但说句公道话贪心本身并不难难的是你不知道这道题该不该用贪心以及排序依据到底是什么。这篇文章我直接按照五级实战的标准把贪心算法最常见的题型、解题模板和我在教学里反复强调的坑全部梳理一遍适合正在备考2025年6月GESP五级的同学直接“抄作业”。作为带过好几轮GESP备考班的老师我见过太多孩子在五级上栽跟头递推没问题枚举也没问题一到贪心就发现—明明思路对样例也过了一交上去就是WA。这篇文章就是要把这些隐蔽的坑一个个挖出来帮你在考场上少走弯路。1. 先搞懂贪心的本质五级考场上的“局部最优”陷阱1.1 贪心算法为什么是五级必考GESP五级的考纲跨度其实挺大从基础排序、结构体到递推、分治、贪心再到简单动态规划基本上是信息学竞赛入门到进阶之间的一个分水岭。贪心算法在这个阶段的位置非常特殊它不像动态规划那样需要定义状态、推转移方程代码写起来往往很短但思维难度反而更高。为什么官方这么偏爱贪心因为贪心考察的是“建模能力”和“证明能力”的雏形。你在考场上看一道题能不能快速判断这是一个贪心问题能不能准确说出“为什么按这个规则排序就是对的”这恰恰是五级真正想筛选的东西。很多同学问过我“五级到底考什么”我的答案是考你能不能用最少的代码解决最优化问题而贪心就是这类问题的典型代表。1.2 三个判定标准什么时候才敢用贪心很多同学最大的困惑是拿到一道题怎么知道能贪心这里我总结三个实际的判定标准你在考场上可以拿这三个标准逐条过一遍。第一问题求的是最值——最大值、最小值、最多能选几个、最少需要几次这是贪心题最明显的特征。第二每一步的选择不会影响后续的决策空间用术语说就是“无后效性”。这个听起来抽象我举个例子你选择先完成哪个活动选完之后剩余的活动选择范围不会因为你这个选择而彻底改变最多是排除掉冲突项这就是无后效性。第三局部最优能推出全局最优。这一点在考场上没法严格证明的话可以用“反例试探法”——按你想到的贪心策略构造一个小数据如果死活构造不出反例那大概率就是对的。这里必须多说一句“看起来对”不等于“真的对”。我见过不少同学在考场上拍脑袋想出一个排序规则样例过了就觉得稳了结果提交之后发现WA得很惨。五级考试里贪心题最容易出的就是这种“假贪心”表面看每一步都在做最优选择但全局并不是最优。1.3 五级常见的“假贪心”陷阱我在教学里反复强调过一类典型题目0-1背包问题。很多同学一看“每种物品只能选一次背包容量有限求价值最大”脱口而出“按价值/重量比从大到小选不就行了”这就是最经典的假贪心。举个具体例子背包容量10有三个物品A重量6价值12B重量5价值10C重量5价值10。按性价比算A最高先选了A剩下容量4什么都选不了总价值12。但正确答案是选B和C总价值20。你看每一步局部最优选性价比最高的反而导致全局不是最优。所以在考场上当你想到一个贪心策略时第一反应应该是找反例而不是马上写代码。找到反例说明这题不能贪心可能是动态规划找不到反例再动手写代码也不迟。2. 高频题型模板区间问题与合并问题2.1 区间调度模板活动安排区间调度是五级最热门的贪心题型没有之一。它的标准形式是有若干个活动每个活动有开始时间s和结束时间t同一时间只能参加一个活动问最多能参加几个活动。这类题的经典解法是按照结束时间从早到晚排序依次选择结束时间最早且与已选活动不冲突的活动。为什么按结束时间排序而不是按开始时间、不是按持续时间关键在于结束时间越早留给后面的时间就越多这是整个策略的核心逻辑。我带你推演一下排序的三种可能按开始时间排序一个从0开始到100的活动会排在最前面选了它后面全废了明显不对。按持续时间排序一个持续1天但横跨全场中间的活动可能先被选它会挡住大量两侧活动也不对。按结束时间排序每次给后面留出最大空间这才对。核心代码模板如下#include bits/stdc.h using namespace std; struct Node { int s, t; } a[1005]; bool cmp(Node x, Node y) { return x.t y.t; // 关键按结束时间排序 } int main() { int n; cin n; for (int i 1; i n; i) { cin a[i].s a[i].t; } sort(a 1, a n 1, cmp); int ans 0, lastEnd -1; for (int i 1; i n; i) { if (a[i].s lastEnd) { // 不冲突注意边界 ans; lastEnd a[i].t; } } cout ans endl; return 0; }这里有个细节一定要记住判断不冲突的条件是a[i].s lastEnd还是a[i].s lastEnd取决于题目说的是“活动结束时间也可以开始另一个活动”还是“不能重叠”。GESP真题里通常用即前一活动结束时刻与后一活动开始时刻相同是可以衔接的但如果你不放心读题时把这个条件圈出来。2.2 区间选点与区间覆盖变体区间问题不只是活动安排还有两个经典变体在五级也经常出现。变体一区间选点。给你若干个区间要求选出尽可能少的点使得每个区间里至少包含一个选出的点。解题思路是将所有区间按右端点从小到大排序然后从第一个区间开始把点选在区间的右端点上同时把所有包含这个点的区间全部标记为“已覆盖”再找下一个未覆盖区间里右端点最小的重复操作。为什么选在右端点因为右端点是当前区间最靠右的位置把它放在这里可以最大概率覆盖到后面那些左端点较小的区间。这个思路和活动安排选最早结束的活动本质上是同构的。变体二区间覆盖。给定一个目标区间用尽量少的已知区间把它覆盖。这个问题的贪心策略是每次在所有左端点不超过当前覆盖右边界的区间中选择右端点最大的那个然后更新覆盖边界。五级如果考到这个变体通常会把区间给你排好序那就更简单了直接线性扫一遍即可。2.3 合并果子类优先队列贪心模板如果你刷过洛谷一定见过P1090“合并果子”这道经典题。它的描述是有n堆果子每次可以将两堆合并成一堆消耗的体力等于两堆质量之和求把所有果子合成一堆的最小体力消耗。这道题的贪心策略极其经典每次选择重量最小的两堆进行合并。为什么因为越早合并的堆后面被重复计算的次数越多每合并一次它的质量就会参与新堆的质量计算所以要把大堆尽量留到最后让它们少参与几次计算。我在课上经常用一个生活化类比你手里有几张账单每付一次款都要交手续费手续费等于账单金额。如果你想省手续费是不是应该先把小额的付掉把大额账单留到最后道理一模一样。代码模板用的是优先队列小根堆注意C里priority_queue默认是大根堆要取最小值需要写成#include bits/stdc.h using namespace std; int main() { int n, x; priority_queueint, vectorint, greaterint pq; // 小根堆 cin n; for (int i 1; i n; i) { cin x; pq.push(x); } long long ans 0; while (pq.size() 1) { int a pq.top(); pq.pop(); int b pq.top(); pq.pop(); ans (a b); pq.push(a b); } cout ans endl; return 0; }这里有一个很重要的细节ans要用long long。n最大可能是几万甚至几十万每次合并的体力值累加之后很容易超过int范围。不少同学五级败就败在这种细节上样例数据小看不出问题一到大数据直接溢出WA。3. 高频题型模板性价比排序、调度与字符串问题3.1 部分背包与性价比排序如果你看到一道题描述里写着“物品可以分割”“可以只取一部分”那它很可能就是部分背包问题也是五级常见的贪心题。它的思路很简单每个物品有重量w和价值v背包容量有限但物品可以切分求能带走的最大价值。这时候贪心策略是成立的按照单位价值v/w从高到低依次装包能全装就全装装不下就装一部分。为什么这里贪心成立而0-1背包不成立因为物品可以分割你不需要面对“选了它导致后面的选不了”这种二选一困境。每一步装当前单位价值最高的物品永远是最优的。实现的时候通常用结构体保存重量、价值、单价然后按单价从大到小排序struct Goods { double w, v, p; // p v / w } g[1005]; bool cmp(Goods a, Goods b) { return a.p b.p; }排序完成后遍历物品计算总价值。注意如果物品切割后价值按比例计算这里建议全程用double避免整数除法丢失精度。3.2 排队打水类调度问题排队打水问题是另一种经典贪心有n个人排队接水第i个人接水需要t_i时间每个人接水时后面的人都要等待求所有人等待时间总和的最小值。直觉告诉你让接水快的人先接。这个直觉是对的。数学上的解释是一个人接水花t分钟那么他后面有k个人在等待这k个人每人都会多等t分钟也就是说他的接水时间会被乘以他后面的人数。为了让这个“系数大的人承担更小的时间”应该把t小的人安排在前。代码写起来就是排序加前缀和统计sort(t 1, t n 1); // 从小到大排序 long long ans 0, cur 0; for (int i 1; i n; i) { ans cur; // 第i个人等待前面所有人的总时间 cur t[i]; // 当前累积接水时间 }注意最后一个人接水时其实还有“接水本身的时间”题目通常只统计“等待时间”所以不需要加最后一个t_i具体以题目要求为准。我把这个写出来是因为有同学经常为了“要不要加最后一个”而纠结其实只要把题目里的“等待”两个字看仔细就清楚了。3.3 最小字典序与删数问题另一类高频贪心是字符串处理典型代表是删数问题给一个数字串或普通字符串从中删掉k个数字使得剩下的数字串保持原有顺序组成的数最小。这里的贪心策略是从左往右扫描如果当前数字比它后面一个数字大就删掉当前数字重复k次如果扫描完还没删够k个就从末尾删。举一个具体例子数字串1432219删3个数字。第1轮14不删43删掉4得132219第2轮13不删32删掉3得12219第3轮12不删22不删相等不删21删掉2得1219最终答案是1219。你如果不信可以自己手动枚举验证这确实是删3个数字能得到的最小结果。代码模板string s, ans; int k; cin s k; for (char c : s) { while (k 0 !ans.empty() ans.back() c) { ans.pop_back(); k--; } ans.push_back(c); } while (k--) ans.pop_back(); // 如果没删够从尾部删 // 去掉前导0如果空了补0 int pos 0; while (pos ans.size() - 1 ans[pos] 0) pos; cout ans.substr(pos) endl;这个模板有几处坑一是必须用ans.back() c而不是如果有相等的数字保留前一个更稳妥因为删后面的不会让数字变小还多消耗一次删除次数二是处理前导0时如果最后只剩“0”ans.size() - 1这个判断会让while失效所以需要额外判断。4. 实战拆解三道典型五级真题带你走完整流程4.1 活动安排从读题到AC的完整推演我就拿最典型的活动安排题来走一遍完整流程。假设题目描述学校在一天内要安排n个活动每个活动有开始时间和结束时间两个活动不能重叠端点可以重合问最多能安排多少个活动。拿到题目之后第一步不是写代码而是给贪心策略找证明。我会这么想如果有一个最优解而它的第一个活动不是结束时间最早的活动那我用结束时间最早的活动替换掉它会不会破坏方案不会因为最早结束的活动的结束时间一定不晚于原第一个活动的结束时间后面所有活动依然可以照常进行。替换之后方案依然合法且数量不变。这样一直替换下去就说明“每次选结束时间最早的活动”的贪心解和某个最优解等价。这个证明思路叫交换论证法五级不要求你写在卷面上但你自己心里必须清楚。然后动手写代码。结构体存s和t排序用sort(a1, an1, cmp)。遍历时用一个变量记录上一个被选活动的结束时间。当前活动开始时间大于等于这个时间就选择它更新结束时间计数加一。代码前面已经给过了这里不再重复。我在班上做过统计第一次做这道题的同学写出来的错误大概有这几种一是cmp函数写成return x.s y.s按开始时间排序小数据碰巧能过一旦构造数据立刻WA二是边界条件判断写成了a[i].s lastEnd少了等于号三是把活动下标从0开始但遍历时用了i n导致越界。这三种都是低级错误但考场上真的会犯。4.2 合并果子为什么每次取最小堆一定最优合并果子的贪心证明比活动安排稍微难一点我用一种容易理解的方式讲。假设当前有若干堆果子它们的重量是w1 ≤ w2 ≤ ... ≤ wn。在一次合并中如果某次操作没有选择最轻的两堆w1和w2而是合并了其他两堆wi和wj那么这次合并的代价是wi wj ≥ w1 w2。关键在于我们可以把这次“合并”的结果与“合并w1和w2”的结果进行比较合并w1和w2后w1w2作为一个新堆重量不超过wiwj。后续不管怎么合并所有操作的总代价都会因为“每个堆被包含的次数”不同而发生变化但可以证明把轻的堆尽量提前合并能让它们被后续合并重复计算的次数最少。这个证明完整写起来要用哈夫曼树的带权路径长度来论证但在五级考场上你只要记住优先队列每次取最小两个这就是哈夫曼编码的思想。实操中我觉得最容易出错的不是算法本身而是对优先队列用法的熟练度。C里小根堆的写法太反直觉了greaterint中间那个尖括号有空格更安全否则编译器在某些C98标准下会报错。另外pq.top()获取的是堆顶元素pq.pop()才是弹出别把顺序搞反。4.3 删数问题字符串贪心的边界处理删数问题是五级字符串贪心的代表题它考察的不只是贪心思维还有字符串处理的边界能力。我亲眼见过有同学核心贪心逻辑全对结果因为没处理前导0丢了分非常可惜。完整的处理逻辑应该是这样的用单调栈思想实现贪心遇到比栈顶小的就让栈顶出栈同时k减一最后如果k还没用完从末尾删删完后去掉前导0如果为空就输出“0”。这里我分享一个测试技巧构造极端数据。比如输入100删除1个数字。按贪心扫描1后面是010所以1被删掉栈里变成00。判断非空去掉前导0后只剩0。如果你没有做去前导0的操作输出00这在严格评判下就是错误。遇到这种极端边界必须在本地先测一遍。5. 考场快速识别与代码模板速查5.1 贪心题的“信号词”识别五级考试的编程题题目描述往往不会直接写“请使用贪心算法”你需要从一些信号词里判断。根据我刷真题的经验以下特征同时出现时贪心概率极高题干出现“最多”“最少”“最大”“最小”这类最优化描述数据范围比较大n在10^5级别甚至更高说明复杂度需要O(n log n)或O(n)动态规划状态往往存不下题目要求你“选择”“安排”“排队”而不是“计算方案数”反过来如果一道题要求输出方案数那基本不是贪心可能是递推或动态规划。如果要求具体方案贪心也可以做但要额外记录选择路径。5.2 常见出题变体与对应策略我在整理历年真题和模拟题时发现贪心在五级的出题变体其实就那几种万变不离其宗变体类型核心策略典型标志词区间调度按结束时间排序活动、会议、课程合并问题优先队列每次取最小合并、搬运、组队部分背包按性价比排序可以分割、取一部分调度等待按处理时间升序排队、等待、接水字符串贪心单调栈扫描删除若干字符、最小数分段切割根据收益差排序切割、分成k段看到这些题目你就往对应模板上套但套模板之前还是要验证“合不合法”也就是找一下有没有反例。如果找到反例立刻转动态规划或其他思路不要在错误的贪心上浪费时间。5.3 错误思路自救指南考场上最怕的不是想不出思路而是想了一个错误思路还坚信不疑。我给自己学生定了一条规矩AC之前必须用构造法检验。具体来说每想出一个贪心策略就手工造一个5到10个元素的小数据用暴力枚举验证贪心结果是不是全局最优。五级的编程题数据范围往往允许你写一个暴力程序对拍这在本地练习时非常有用。真到了考场如果贪心思路被推翻而你又不确定动态规划怎么写还有一个应急策略写下能得部分分的暴力代码。GESP的评分是分段给分的样例、小数据都能拿到一部分分。先把暴力分拿到手再回头想正解这是竞赛场上的通用打法。6. 避坑清单五级考生最常见的几个翻车点6.1 排序的cmp写错导致全盘皆输贪心题几乎都要排序而排序的比较函数是最容易翻车的地方。我总结了三个高频错误一是忘记加static或写错参数类型。在类内部定义cmp时需要静态但五级考生通常直接在全局写这点倒还好真正致命的是参数类型必须和sort传入的容器元素类型完全一致。你定义的结构体是Nodecmp参数就必须是Node写错一个字母编译就报错但考场上编译报错已经浪费了宝贵时间。二是比较方向搞反。return x.t y.t是升序从小到大return x.t y.t是降序从大到小。活动安排要升序部分背包要降序我见过有同学把两个模板记混导致活动安排按结束时间降序排序输出的答案简直是灾难。三是相等情况没有处理。sort排序要求cmp严格弱序如果x.t y.t时返回true可能引发未定义行为导致排序结果随机。稳妥的写法是bool cmp(Node a, Node b) { if (a.t ! b.t) return a.t b.t; return a.s b.s; // 次级排序保证严格弱序 }6.2 数据类型溢出和整除精度五级的数据范围已经不是“小打小闹”了n10^5、数值在10^9量级很常见。累加结果、乘积结果都可能超出int范围。建议所有可能累加或相乘的变量直接用long long最多多占点内存但能避免最恶心的WA。在部分背包题里注意两个整数相除会得到整数v / w如果两个都是int单价可能被截断成0导致排序完全失效。要么把v和w都转成double要么用交叉相乘比较a.v * b.w b.v * a.w后者更精确还避免了浮点误差。6.3 边界条件越界、空串、端点重合边界条件是贪心题的第二大扣分点。区间问题要注意端点需要不需要删数问题要注意删完后字符串为空合并问题要注意n1时不需要任何合并答案直接是0部分背包要注意背包容量为0的情况。这些边界条件看起来琐碎但GESP的测试数据非常喜欢塞这类边界数据。我的建议是本地测试时每组数据都额外测一下n0、n1、所有值相等、逆序排列这四类极端情况能帮你挡掉至少一半的WA。最后再分享一个小技巧GESP五级的选择题同样会考贪心概念比如“以下哪道题适合用贪心算法”“贪心算法与动态规划的区别是什么”。备考编程题的同时把每种题型对应的贪心策略背熟选择题基本就是送分。我在实际教学里发现凡是能把这篇文章的模板吃透的同学刷历年五级真题的通过率基本都在九成以上你对贪心的理解每深一层五级通过的概率就大一分。