我把GESP五级的真题和模拟题翻来覆去做过好几遍之后发现一个特别明显的规律凡是考算法思想的大题十道里至少有六道能闻到贪心的味道。考生圈子里甚至流传着一句话——五级能不能过很大程度上看贪心学得透不透。这个说法不算夸张区间调度、找最值、给一堆条件让你做选择背后几乎都是贪心的影子。而且贪心的代码往往不长核心逻辑可能就十几行但关键在于“你到底贪得对不对”。这篇内容就是围绕GESP五级的贪心算法考点来写的。我会把贪心到底是什么、哪些题型在五级里高频出现、每类题的关键策略是什么、代码怎么写、需要注意哪些边界都掰开揉碎讲清楚。适合两类人一是正在备赛五级、想系统过一遍贪心考点的同学二是代码能写但总是“样例对、提交错”一遇到贪心就凭感觉乱选策略的选手。看完之后你至少能建立起一套判断“能不能贪”的方法而不是看到题目就瞎猜。1. 为什么说贪心是五级的分水岭1.1 五级考点里的“贪心权重”GESP五级的考纲覆盖面其实不小排序进阶、二分答案、动态规划入门、递归回溯、贪心算法、数据结构基础都在里面。但如果你真的去统计历年题型分布会发现在算法策略类题目中贪心的出场频率明显压过其他。原因也很简单五级不是六级动态规划不会考太深而贪心正好处在一个“比模拟有思想、比DP好实现”的中间位置。具体到卷面贪心一般出现在两个位置选择题里用概念判断你是否理解贪心的适用条件编程题里让你独立写出贪心策略并处理边界数据。编程题只要考贪心分值基本在20分上下一旦策略选错整道题就是零分因为样例给得再友好也救不了错误思路。我辅导过不少备赛的同学有一个现象特别普遍排序和二分大家都能刷得很熟练一到贪心就开始“手感失灵”。原因不是代码能力不够而是贪心这种思想本身不像是“知识点”更像是一种需要大量案例喂出来的直觉。所以刷贪心题没有足够的样本量真的会一直处于“似懂非懂”的状态。1.2 为什么贪心学起来有点玄很多同学觉得贪心玄是因为它们在课堂上看到的贪心证明通常长这样“我们首先证明最优解具有贪心选择性然后证明最优子结构……”这些话写在课本上没问题但对于一个要在一小时内写完四道题的考生来说根本不会在考场上做形式化证明。更麻烦的是贪心的正确性没有一个通用判定公式。同样是“每次选最大的”有些题目是对的有些题目就是错的。比如背包问题里“每次选单位价值最高的物品”在完全背包可拆分时是对的但在0-1背包里就是错的。同一个动作换个约束条件结论天翻地覆。这种特性让缺乏经验的学生非常容易踩坑。我一直觉得对五级考生来说学贪心不需要掌握严格的数学证明但必须掌握两种能力第一能说出“我为什么这么贪”的直观理由第二能构造一个反例来测试自己的策略是否站得住脚。这两点练好了考场上就够用了。后面我会专门讲判断策略对错的实操方法比背证明结论管用得多。2. 贪心算法的本质先想清楚“贪什么”2.1 一句话版本的贪心贪心算法通俗点讲就是你面对一个复杂问题时不管全局多复杂每一轮只盯着“当前看起来最好的选择”去下手并且一旦做了选择就坚决不回头。它和动态规划最大的区别就在这里动态规划会做完所有可能的选择再比较贪心只做一条路走到黑。举个例子你就懂了。假设你现在是个小老板桌上有一堆订单每个订单都有一个截止时间和一个利润你一天只能做一个订单要让自己赚得最多。如果按“今天最急的”来做可能忙了一整天只赚到一个小单如果按“利润最高的”来做可能好几个优质订单都挤在同一天最后期限根本来不及。贪心的关键就是先想清楚到底应该按照什么规则来排序筛选才能让每一步的选择都对最终答案有正贡献。这种“当前最优”不一定导致“全局最优”所以贪心算法不能随便套。但在GESP五级的范围内题目设计者通常会确保存在一个明确的贪心策略而且这个策略往往跟排序有关。这也是为什么我说排序是贪心的半条命——五级的贪心题十道里至少有八道要先排序再做选择。2.2 能使用贪心的两条铁律判断一道题能不能用贪心不需要背高深理论记住两条特征就行。第一条叫无后效性当前这一步做完了之前怎么选的已经不影响后续决策的判断。说人话就是——你只关心“现在还剩哪些可用资源”不关心这些资源是怎么被消耗掉的。比如活动安排中你选了某个时间段的活动之后后继只需要看剩余活动的开始时间有没有落在已选活动结束时间之后完全不需要回溯调整。第二条叫局部最优对全局有贡献每一步选出的当前最优凑在一起就是最终最优。这个性质说起来玄但做题时可以通过构造反例来检验——如果存在某个反例当前的“最优动作”会让总结果变差那这题就不能贪心赶紧转DP。这里我补充一个非常实用的经验GESP五级里能贪心的题95%以上都满足一个模式——“按某个关键字排序然后依次处理”。所以你做题时如果完全没有头绪先试着列出所有排序关键字比如时间、截止日期、利润、重量、人数、数量。然后问自己假设我按这个关键字从小到大处理每一步能得到什么好处能把这个因果关系想通题目基本就解了一半。2.3 手写一个“贪心是否正确”的小实验我教学生判断贪心策略对不对会让他们做一个小实验拿生成器随机造几组小数据然后把贪心结果和暴力枚举的结果对比。这个实验不用上考场也能做甚至用手都能笔算几组。举个例子假设有个题说“从一堆数里选出若干个使总和最大但相邻的两个数不能同时选”。你心里冒出一个贪心策略“每次选当前最大的数选完之后把它的两个邻居也删掉。”这个策略听起来合理吗我们来构造一个反例数组是[4, 2, 6, 2, 4]。按刚刚的策略先选中6删除它旁边的两个2剩下[4, 4]于是选4和4总收益是14。但实际上最优选择是4 6 4 14也是14看起来好像对。再换一个例子[5, 4, 2, 2, 2, 4, 5]先选5删掉4剩下[2, 2, 2, 4, 5]再选5删掉4剩下[2,2,2]再选2、2、2不对选2会删掉旁边的2结果变成55212。但最优其实是选开头5、中间的两个4和结尾5544518。看贪心翻车了。这种方式比死记“什么题型用什么策略”要可靠得多。你在平时练习时就应该养成“随手找反例”的习惯。到了考场上虽然没有生成器和暴力程序但你可以用几个小规模样例手算如果样例过不了说明策略有问题该换思路。3. 五级常考的贪心类型与识别技巧3.1 区间调度类按结束时间排序区间调度在五级里出现频率极高典型问法是给你一堆活动每个活动有开始时间和结束时间一个人最多能参加多少个互不重叠的活动或者换成会议室、排练室、直播档期的场景但本质一模一样。这类题的贪心口诀就是四个字按结束时间早的优先。原理很简单结束时间越早活动后面的空余时间就越长给你留的机会越多。反过来如果优先选开始时间最早的很容易选到一个耗时很长的大活动把一天全占掉反而损失更多。这里有个很多人会踩的点排序关键字和排序方向搞混。区间调度必须按结束时间升序不是按开始时间也不是按时长。为什么看一个例子活动A从0到10活动B从1到2活动C从3到4。按开始时间排是A、B、C选了A后B和C都选不了答案只有1个按结束时间排是B、C、A先选B再选C答案是2个。同样的数据排序关键字不同结果天差地别。3.2 排序决策类让“代价”小的先做还有一类高频贪心叫“排队优化”典型场景是几个人排队接水每人需要不同的时间怎么安排让总等待时间最短或者有若干任务每个任务有耗时和截止时间怎么安排让所有任务的超时总和最小这类题的策略核心是把“代价小”或者“贡献大”的对象排到前面去。排队接水的场景里让接水速度快的人先接后面所有人的等待时间都能更快减少。因为总等待时间 每个人的接水时间 × 在他身后排队的人数身后排的人越多这个人对总时间的“放大系数”越大所以应该把耗时短的人放在放大系数最大的位置。做这类题需要额外注意计算的数据类型。人数达到万级、亿级时总等待时间会非常容易超过int范围必须用long long。我见过很多同学策略全对就因为在累加这一步偷懒用了int结果大样例直接溢出白白丢掉满分。3.3 堆维护类不断取最小/最大第三种高频题型需要借助堆优先队列来维护“当前最优”。最经典的原型是合并果子n堆果子每次合并两堆合并代价是两堆数量之和求把所有果子合成一堆的最小总代价。这个题的贪心策略是每次挑重量最小的两堆合并。为什么因为每次合并的代价会作为“一部分”继续参与后续合并如果一开始就把大堆合进去了大堆的重量会被反复累计到后续的代价里总代价就会爆炸。而优先挑小的堆合并沉没成本就能压到最低。写代码时就别再每次O(n)扫一遍找最小了那时间复杂度直接退化成O(n²)数据一大必超时。正确做法是用priority_queue声明小根堆每次从堆顶取两个元素合并后把新堆重新压入代码复杂度O(nlogn)。在五级考场上看到“反复选当前最大/最小”的题目第一反应就应该是堆。3.4 容易误判成贪心的题型贪心最大的坑不是不会写而是以为自己是贪心其实是伪贪心。五级的考纲里有几个经典伪贪心场景值得单独记一下。第一个是0-1背包。物品不可拆分你不能只拿一个物品的一部分这时候按单位重量价值从高到低贪心选结果可能是错的。经典的例子是背包容量10物品A重量6价值12物品B重量5价值10物品C重量5价值10。按单位价值排A、B、C选A后剩余容量4什么都装不了总价值12但最优方案是选B和C总价值20。看到这个反例你就明白为什么0-1背包要用DP而不是贪心。第二个是“数字游戏”里删掉k个数让剩余数字最小这类问题。有人会觉得每次删掉当前最大的数就行但实际上要考虑位置关系需要维护一个单调栈。这种题表面上是“每次最优”实际上决策会和已经选过的东西产生依赖就不是标准的贪心能解决的。所以遇到题目先别急着想“每次选什么”先判断“这次选择会不会影响后续选择的信息结构”。如果会大概率不是贪心。4. 四道经典题逐行拆解从读题到AC这一章我用四道GESP五级难度最匹配的经典题型把读题、分析、编码、验证的完整流程走一遍。代码以C为例因为五级主流的考试语言就是C但如果你的主力语言是Python思路完全通用只需要把排序和堆的写法对号入座就行。4.1 活动安排区间调度模板题目描述模拟题在一间教室里有n个活动要办每个活动给出开始时间l[i]和结束时间r[i]。问最多能安排多少个互不重叠的活动允许一个活动结束的同一时刻另一个活动开始。先分析这道题就是区间调度的模板。我们决定采用“按结束时间升序排序从左到右扫描能选就选”的策略。这个策略为什么成立假设最优方案里第一个活动不是结束最早的那我把它替换成结束更早的活动绝不会让后续可选活动变少反而可能变多。用这个逻辑一路替换下去最优方案可以被改造成“每次选结束最早”的方案而不变差所以贪心成立。代码实现#include bits/stdc.h using namespace std; struct Node { int l, r; }; int main() { int n; cin n; vectorNode a(n); for (int i 0; i n; i) { cin a[i].l a[i].r; } sort(a.begin(), a.end(), [](const Node x, const Node y) { return x.r y.r; }); int ans 0; int lastEnd -1e9; for (const auto e : a) { if (e.l lastEnd) { ans; lastEnd e.r; } } cout ans endl; return 0; }几个关键细节lastEnd初始化为一个很小的负数保证第一个活动一定被选中。判断条件是e.l lastEnd因为题目允许“结束时刻等于开始时刻”的活动衔接。如果你的题目要求严格错开就把改成。这种“一字之差”的边界就是考试里最容易扣分的地方。4.2 合并果子堆优化的贪心题目描述模拟题有n堆果子第i堆有a[i]个果子。每次可以把任意两堆合在一起消耗的体力等于两堆果子数量之和。要把所有果子合成一堆求最小总体力消耗。思路由于总消耗等于合并过程中产生的所有中间和相加为了让大的数尽量少参与累加每次就应该挑当前最小的两堆来合并。这个策略和哈夫曼编码的思想完全一致越小的东西放在越深的合并路径里越不会被反复计算。代码实现#include bits/stdc.h using namespace std; int main() { int n; cin n; priority_queueint, vectorint, greaterint pq; for (int i 0; i n; i) { int x; cin x; pq.push(x); } long long ans 0; while (pq.size() 1) { int x pq.top(); pq.pop(); int y pq.top(); pq.pop(); int sum x y; ans sum; pq.push(sum); } cout ans endl; return 0; }这里的重点priority_queue默认是最大堆要用priority_queueint, vectorint, greaterint来声明小根堆很多新手会在这里卡住。ans必须用long long因为极端情况下n100000、每堆1个果子来自顶层的和会达到n×n量级也就是约1e10远超出int范围。这个坑我在很多同学的提交记录里见过属于“代码一眼看过去挺对大样例就全错”的典型。4.3 跳跃游戏边界与最远可达题目描述模拟题有n个格子排成一条线编号从1到n。格子上写着一个数a[i]表示从该格子可以向右跳任意不超过a[i]的距离。从第1格出发要跳到第n格最少需要跳几次。数据范围保证一定可以到达。这道题看数据范围就知道不可能是DPn可以达到几十万DP O(n²)必炸。所以要用贪心思路每次在“当前这一步能达到的范围”内找到下一跳能到达的最远位置然后跨到那个范围去。记录两个变量当前步数的覆盖边界curEnd以及当前覆盖范围内能到达的最远位置maxReach。遍历过程中不断更新maxReach一旦贪心指针到了curEnd说明必须跳一步此时把curEnd更新为maxReach步数加一。有人会问为什么遍历到curEnd才加步数而不是一看到maxReach更新就加因为你在当前覆盖范围内移动时仍然是在用“同一跳的余力”不需要额外步数。只有当你把这个范围内的所有格子都检查完发现边界到头了才被迫跳出下一步。代码实现#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint a(n); for (int i 0; i n; i) { cin a[i]; } int steps 0; int curEnd 0; int maxReach 0; for (int i 0; i n - 1; i) { maxReach max(maxReach, i a[i]); if (i curEnd) { steps; curEnd maxReach; } } cout steps endl; return 0; }重点循环只走到n-2因为最后一个格子不需要再跳出去。步骤数在icurEnd时递增这里的逻辑要反复理解是整道题最绕的地方。背模板没有用必须自己动手模拟几组数据比如a[2, 3, 1, 1, 4]手写一遍会发现结果是2和直觉吻合。4.4 排队打水排序公式推导题目描述模拟题有n个人在同一个水龙头排队打水第i个人需要t[i]分钟。所有人同时到达问怎样安排打水顺序使得所有人的等待时间之和最小不包括自己打水的时间。请你输出最小等待时间总和。思路假设一个顺序是p[0], p[1], …, p[n-1]那么第i个人的等待时间是前面所有人的打水时间之和即t[p[0]] t[p[1]] … t[p[i-1]]。总等待时间可以写成第0个人对后面n-1个人都有贡献第1个人对后面n-2个人有贡献以此类推。所以总等待时间 t[p[0]]×(n-1) t[p[1]]×(n-2) … t[p[n-2]]×1。要让这个式子最小就让系数大的位置分配耗时小的人。所以策略就是按打水时间升序排序。代码实现#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long t(n); for (int i 0; i n; i) { cin t[i]; } sort(t.begin(), t.end()); long long ans 0; for (int i 0; i n; i) { ans t[i] * (n - i - 1); } cout ans endl; return 0; }排序之后第i个人的系数是n-i-1。代码里直接套公式求和即可。这个公式建议自己推导一遍因为考场上万一题目换成了“水龙头有两个”“打水时间含接水时间”等变体你不理解公式就只能瞎改容易错。另外还是那个老提醒用long long不要问为什么。5. 贪心与动态规划边界在哪里5.1 五级考卷上两者的关系贪心和动态规划在考卷上经常同时出现因为它们都解决“多阶段决策问题”。但五级的动态规划考得比较基础像数塔路径、最长上升子序列这类状态转移比较直白。而贪心题往往更考验“灵光一现”的策略选择。两者不是对立的动态规划中有时会用到贪心思想去优化状态转移贪心题的错误答案也经常被DP纠正。所以我不主张你只盯着“这题能不能贪心”而是建议你建立一条判断链路如果题目规模允许O(n²)级别的状态枚举并且每一步的选择会影响后续状态空间优先考虑DP如果题目数据量很大或者你发现存在一个“无论怎么选当前最优总不劣于其他选择”的明确顺序那么贪心就是更优解。5.2 区分贪心与DP的几个经验法则总结一下我在讲题时反复强调的几条判断经验基本覆盖了五级的常见场景。第一看数据范围。一般来说n达到1e5甚至更大的题目如果AC要求时间在秒级以内那它想考察的多半是贪心或二分而不是DP。因为很多DP的时间复杂度下界就是O(n²)或O(n×m)这种量级在n1e5时就很难受了。第二看选择的依赖性。如果每一步选择只决定“剩下可选集合”而不影响已经做完的选择的收益就有贪心的味道。如果当前选择会让之前的努力作废或收益改变那就要用DP把状态记录下来。第三看结果的最优性数量级。题目问“最少”“最多”“最大”“最小”这是贪心和DP共用的问题形态。但如果问“方案总数”那几乎肯定不是贪心因为贪心只能构造一种方案不会计数。5.3 一张反例对照表我把常见的“看似贪心实则不能贪”的题型整理成一张对照表方便你复习时快速回忆。题型错误贪心策略错误原因正确方向0-1背包按单位重量价值排序物品不可拆分局部最优可能挤掉组合收益动态规划最长上升子序列每次选当前尽量小的数当前选择会影响后续上升空间且状态依赖历史动态规划或贪心二分变体删数最小问题每次删当前最大数字高位对结果影响大需要按位比较而非按值比较单调栈带截止时间的任务排程按截止时间最早排序需要考虑任务时长和收益的组合按优化目标设计排序最小生成树每次选权值最小的边而不判断成环可能形成环导致局部选边失效需要并查集配合Kruskal这张表不是为了让你背诵而是提醒你看到类似的对策一定要在脑子里过一遍“是否存在反例”。平时练习时吃了亏考场上才能避开。6. 考场实战与刷题路线6.1 考场上遇到贪心题的标准动作进了考场时间紧张不可能像平时做题那样慢条斯理地推演。我给自己的学生定了四步走你们可以直接抄作业。第一步30秒内判断题型。看到“最多”“最少”“最大”“最小”这些字眼先把贪心列为候选。接着看数据范围如果n很大比如1e5大概率不是DP把贪心优先级提到最高。第二步用一句话写出贪心策略。写不出来说明你没想清楚这也是一种信号。比如“按结束时间早的排能选就选”“每次合并最小两堆”“先做截止时间早且耗时短的”。一句话能写出来思路就有了。第三步手造两组小数据验证。一组用随机感觉编的普通数据另一组是刻意找极端数据。极端数据的手法一般是让两个对象特征完全对立一个时间短价值高一个时间长价值低或者让“局部最优”非常诱人看它会不会把全局带偏。如果极端数据能撑住策略基本靠得住。第四步写代码前先想清楚三个细节排序方向是什么要不要用堆累加结果要不要long long。这三个细节定下来再动手敲键盘。6.2 常见问题与避坑速查表把我在批改代码过程中遇到的高频错误整理成一个速查表你按这个对照自己有没有踩坑。症状可能的原因解决办法样例对但提交WA排序关键字选错比如区间调度按了开始时间回到策略验证环节检查“贪什么”大数据超时每一步用循环找最大最小值换priority_queue维护降到O(nlogn)答案比预期大累加变量用了int溢出把所有会增长到1e9以上的变量统一用long long边界样例错误lastEnd初始值不对或首尾判断条件写错把边界条件写成注释逐行读一遍贪心思路翻车题目不满足贪心条件被伪贪心误导构造反例验证不行赶紧转DP排序方向反了升序降序没想清楚根据策略推导一遍公式不要凭感觉这个表里的前三条占了考试失分的绝大多数。尤其是“答案比预期大”这个问题很多同学一直到赛后看数据都发现不了因为小数据根本测不出溢出只有上到几十万规模的极端数据才会爆炸。6.3 从零到五级的贪心刷题路线如果你距离考试还有一段时间不要盲目随机刷题按下面三个阶段推进效率会高很多。第一阶段把“排序贪心”的基础模板练透。活动安排、排队打水、幸存者游戏、按区间合并最小覆盖等每道题都严格走一遍“写策略→验证→写代码→改错”的流程。这个阶段的目的是建立条件反射看到排序相关关键字能迅速意识到后面的处理逻辑。第二阶段练习需要堆配合的贪心。合并果子类的题目是这一阶段的核心。你可以把所有“每次取两个合并”的变体题都拿出来练比如石子合并、砌墙费用、最小连接缆线等。这一阶段掌握后你就具备处理动态变化集合的能力了。第三阶段用混合题训练判断力。把贪心和动态规划、模拟题放在一起刷强迫自己先做题型判断再动手。这一步非常关键因为考场上不会有哪个按钮告诉你“这题是贪心”所有的判断都要靠你自己完成。建议每次做完题后在题解里写一句话“这题为什么能用贪心/为什么不能”长期积累下来思维会变得清晰很多。在带学生的过程中我体会到一件事贪心这道坎跨过去的人会越学越轻松因为后面学图论最短路、学最小生成树时全都依赖贪心思维。跨不过去的人即使硬背了几套模板遇到新题还是会懵。所以如果你正在为五级焦虑别急先把一道活动的贪心题从头到尾“为什么这么贪”想明白这个胜仗打下来后面就有了底气。我个人始终觉得贪心不是靠天赋是靠案例和反思堆出来的手感——刷够题、想透理由、踩过坑五级的贪心题在你眼里会变成送分题。