GESP五级贪心算法全解：从区间调度到堆优化，掌握考点与避坑技巧

我把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，结果变成5+5+2=12。但最优其实是选开头5、中间的两个4和结尾5，5+4+4+5=18。看，贪心翻车了。

这种方式比死记“什么题型用什么策略”要可靠得多。你在平时练习时，就应该养成“随手找反例”的习惯。到了考场上虽然没有生成器和暴力程序，但你可以用几个小规模样例手算，如果样例过不了，说明策略有问题，该换思路。

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; vector<Node> 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_queue<int, vector<int>, greater<int>> 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_queue<int, vector<int>, greater<int>>来声明小根堆，很多新手会在这里卡住。ans必须用long long，因为极端情况下n=100000、每堆1个果子，来自顶层的和会达到n×n量级，也就是约1e10，远超出int范围。这个坑我在很多同学的提交记录里见过，属于“代码一眼看过去挺对，大样例就全错”的典型。

4.3 跳跃游戏：边界与最远可达

题目描述（模拟题）：有n个格子排成一条线，编号从1到n。格子上写着一个数a[i]，表示从该格子可以向右跳任意不超过a[i]的距离。从第1格出发，要跳到第n格，最少需要跳几次。数据范围保证一定可以到达。

这道题看数据范围就知道不可能是DP：n可以达到几十万，DP O(n²)必炸。所以要用贪心思路：每次在“当前这一步能达到的范围”内，找到下一跳能到达的最远位置，然后跨到那个范围去。记录两个变量：当前步数的覆盖边界curEnd，以及当前覆盖范围内能到达的最远位置maxReach。遍历过程中不断更新maxReach，一旦贪心指针到了curEnd，说明必须跳一步，此时把curEnd更新为maxReach，步数加一。

有人会问：为什么遍历到curEnd才加步数，而不是一看到maxReach更新就加？因为你在当前覆盖范围内移动时，仍然是在用“同一跳的余力”，不需要额外步数。只有当你把这个范围内的所有格子都检查完，发现边界到头了，才被迫跳出下一步。

代码实现：

#include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> 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，因为最后一个格子不需要再跳出去。步骤数在i==curEnd时递增，这里的逻辑要反复理解，是整道题最绕的地方。背模板没有用，必须自己动手模拟几组数据，比如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; vector<long 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)，这种量级在n=1e5时就很难受了。

第二，看选择的依赖性。如果每一步选择只决定“剩下可选集合”，而不影响已经做完的选择的收益，就有贪心的味道。如果当前选择会让之前的努力作废或收益改变，那就要用DP把状态记录下来。

第三，看结果的最优性数量级。题目问“最少”“最多”“最大”“最小”，这是贪心和DP共用的问题形态。但如果问“方案总数”，那几乎肯定不是贪心，因为贪心只能构造一种方案，不会计数。

5.3 一张反例对照表

我把常见的“看似贪心实则不能贪”的题型整理成一张对照表，方便你复习时快速回忆。

这张表不是为了让你背诵，而是提醒你：看到类似的对策，一定要在脑子里过一遍“是否存在反例”。平时练习时吃了亏，考场上才能避开。

6. 考场实战与刷题路线

6.1 考场上遇到贪心题的标准动作

进了考场，时间紧张，不可能像平时做题那样慢条斯理地推演。我给自己的学生定了四步走，你们可以直接抄作业。

第一步，30秒内判断题型。看到“最多”“最少”“最大”“最小”这些字眼，先把贪心列为候选。接着看数据范围，如果n很大，比如1e5，大概率不是DP，把贪心优先级提到最高。

第二步，用一句话写出贪心策略。写不出来，说明你没想清楚，这也是一种信号。比如“按结束时间早的排，能选就选”“每次合并最小两堆”“先做截止时间早且耗时短的”。一句话能写出来，思路就有了。

第三步，手造两组小数据验证。一组用随机感觉编的普通数据，另一组是刻意找极端数据。极端数据的手法一般是：让两个对象特征完全对立，一个时间短价值高，一个时间长价值低；或者让“局部最优”非常诱人，看它会不会把全局带偏。如果极端数据能撑住，策略基本靠得住。

第四步，写代码前先想清楚三个细节：排序方向是什么，要不要用堆，累加结果要不要long long。这三个细节定下来，再动手敲键盘。

6.2 常见问题与避坑速查表

把我在批改代码过程中遇到的高频错误整理成一个速查表，你按这个对照自己有没有踩坑。

这个表里的前三条占了考试失分的绝大多数。尤其是“答案比预期大”这个问题，很多同学一直到赛后看数据都发现不了，因为小数据根本测不出溢出，只有上到几十万规模的极端数据才会爆炸。

6.3 从零到五级的贪心刷题路线

如果你距离考试还有一段时间，不要盲目随机刷题，按下面三个阶段推进，效率会高很多。

第一阶段：把“排序+贪心”的基础模板练透。活动安排、排队打水、幸存者游戏、按区间合并最小覆盖等，每道题都严格走一遍“写策略→验证→写代码→改错”的流程。这个阶段的目的是建立条件反射：看到排序相关关键字，能迅速意识到后面的处理逻辑。

第二阶段：练习需要堆配合的贪心。合并果子类的题目是这一阶段的核心。你可以把所有“每次取两个合并”的变体题都拿出来练，比如石子合并、砌墙费用、最小连接缆线等。这一阶段掌握后，你就具备处理动态变化集合的能力了。

第三阶段：用混合题训练判断力。把贪心和动态规划、模拟题放在一起刷，强迫自己先做题型判断再动手。这一步非常关键，因为考场上不会有哪个按钮告诉你“这题是贪心”，所有的判断都要靠你自己完成。建议每次做完题后在题解里写一句话：“这题为什么能用贪心/为什么不能”，长期积累下来，思维会变得清晰很多。

在带学生的过程中，我体会到一件事：贪心这道坎，跨过去的人会越学越轻松，因为后面学图论最短路、学最小生成树时全都依赖贪心思维。跨不过去的人，即使硬背了几套模板，遇到新题还是会懵。所以如果你正在为五级焦虑，别急，先把一道活动的贪心题从头到尾“为什么这么贪”想明白，这个胜仗打下来，后面就有了底气。我个人始终觉得，贪心不是靠天赋，是靠案例和反思堆出来的手感——刷够题、想透理由、踩过坑，五级的贪心题在你眼里会变成送分题。