GESP五级通关秘籍贪心算法中的“损失最小化”到底怎么破每年GESP五级考完总有一批学生出来就吐槽“贪心我也学了题也刷了怎么一上考场还是不知道先排哪个序、选哪个局部最优”尤其是碰到“代价最小化”“损失最小化”这种表述的题目很多人第一反应就是懵——因为教材上讲的贪心基本都是“收益最大化”比如最大价值、最长区间、最多活动这类一旦题干反过来让你最小化代价、最小化损失很多人就开始凭感觉乱试了。其实“损失最小化”是贪心算法里非常经典的一类模型它跟“收益最大化”在思路上完全是镜像关系。GESP五级的真题和模拟题里排队接水、删区间使剩余区间不重叠、多人过桥这些题目本质上都是损失最小化问题。把这一块彻底吃透五级考试的贪心部分基本上就能拿稳了。这篇文章我会从概念讲到证明从代码讲到考场避坑争取让你看完就能直接上手做题。1. 先把概念说透损失最小化到底在解决什么问题1.1 从“赚到的”和“花掉的”两个角度理解贪心先说个生活化的类比。假设你一天要做5件事每件事耗时不同你希望“一天结束前完成的任务数量最多”这时候你要做的贪心是什么优先做耗时短的——这是经典的“活动安排”思路。但如果反过来每件事都固定有截止时间一旦超时就罚钱你希望“被罚的钱最少”这时候你优先做哪件肯定不是无脑做耗时短的而是要综合考虑截止时间和耗时。这就是损失最小化和收益最大化的本质区别收益最大化问题里答案往往藏在“先做性价比最高的”而损失最小化问题里你要在“当前损失”和“未来损失”之间做权衡贪心策略往往体现在“先把会造成最大损失的解决掉”或者“把代价最小的优先处理”。再回到GESP五级的真题场景。五级考试里最常出现的损失最小化题目就是“排队接水”有n个人排队接水第i个人接水需要t_i分钟每个人等待的时间都要算进总代价问所有人等待时间总和最小怎么排队。这道题几乎所有教材都会讲解法是“按接水时间从短到长排队”。但你有没有想过为什么要这样排随机选两个人A和B接水时间分别是a和b且a b。如果A排在B前面B的等待时间就要多a分钟如果B排在A前面A的等待时间就要多b分钟。前者比后者多等a - b分钟。所以要总等待时间最小必然是把耗时短的那个人排前面。这个“交换两个相邻元素看差异”的方法就是贪心证明里最常用的交换论证法后面第五节我会详细展开。1.2 损失最小化其实是收益最大化的“镜像”很多同学没有意识到一个问题里的“损失”换个说法可能就变成了收益。举例来说还是排队接水如果问你“所有人等待时间总和最小”这是损失最小化。但如果你把问题改成“假设每个人都有一个固定的价值问怎么排队让总价值最大化”它就可能变成一个不同的贪心——这时候就不是只看时间了要看“价值/时间”的比值。GESP五级题目里经常会用这种“镜像关系”来迷惑考生。同一个模型换个说法贪心策略完全不同。所以拿到题目第一步永远不是写代码而是先问自己三个问题这个题的目标到底是最大化什么还是最小化什么如果我选择某个方案付出的代价是什么这个代价跟哪些因素有关排序依据是什么把这三个问题想清楚贪心题就成功了一半。1.3 什么样的题会用到“代价最小化”模型我总结了一下GESP五级以及同类考试里常见的损失最小化题型大致有这几类题目类型典型描述贪心策略排队问题n个人排队每人服务时间不同总等待时间最小时间短的先服务区间取舍删掉最少的区间使剩余区间互不重叠按结束时间排序贪心任务调度任务有截止时间和延误代价总延误最小按截止时间排序或按代价大小处理过桥问题多人过桥一次最多两人需持灯往返总时间最短分情况比较两种策略最小化删除代价数组删元素使满足某种性质删除代价最小通常用单调栈或优先队列你注意看前三类在GESP真题里出现频率非常高后面我会挑最典型的两个模型拆开讲透代码也给到可以直接背的程度。2. 排序贪心最核心的武器一次讲明白2.1 排队问题等待总时间最小化这是GESP五级贪心里的“入门题”也是很多学校信息学社团的第一道贪心题。题目描述基本是这样的n个人排队接水第i个人需要t_i分钟每个人的等待时间是从他开始排队到他接到水的总时长问怎么排队能让所有人等待时间总和最小。直接上结论按t从小到大排序。为什么不对所有人统一按时间长的先因为“等待时间的总和”里越靠前的人影响的人越多。第1个人只影响自己第2个人影响自己和后面所有人第n个人影响所有人。如果让一个耗时巨长的人排前面他后面每个人都要白白多等那么久这个代价是乘法级别的增长。用严格一点的方式表述如果排队顺序是p_1, p_2, ..., p_n那么总等待时间是T t[p_1] * (n - 1) t[p_2] * (n - 2) ... t[p_n] * 0看到没有第k个位置的人他的耗时会被乘以他后面的人数。所以要让总时间小就必须让耗时短的人尽量往后排不对——注意这里是乘以“后面的人数”也就是说越靠前的人权重越大n-1最大所以耗时越短的人应该放在权重大的位置。这就是为什么按耗时升序排。2.2 排序方向的决定方法三种常见错误要避免这里我要专门说一下排序方向因为这是损失最小化问题里最容易翻车的点。GESP五级考生做错排队题九成的原因是排序方向搞反了。我见过三种典型错误第一种想当然觉得“时间长的先走后面的人等的时间就少”实际上时间长的先走后面每个人都要被这个长耗时拖累总等待时间反而大。第二种把公式记成乘以“前面的人数”然后得出按耗时降序排的结论这种情况下你至少证明过程是严谨的只是原题看错了——注意有的题目问“总等待时间”有的题目问“总完成时间”两者排序方向一样都是升序但如果问的是“平均等待时间”也是升序千万不要被换了个说法带偏。第三种把“等待时间”等同于“服务时间总和”。等待时间不是累加每个人耗时那么简单而是对每个人而言“他到达后到开始被服务之间的时间”排队接水场景中第i个人的等待时间等于排在他前面所有人的耗时之和不是他自己的耗时。那排序方向到底怎么定我给你们一个通用方法假设两个相邻元素x和y交换它们俩的位置不影响其他元素分别算出“x在y前”和“y在x前”两种方案的代价比较大小取更小的方案成立的不等式就是排序依据。这招叫相邻交换法几乎能解决所有排序类贪心。2.3 代码实现与long long陷阱排队接水这类题的代码很短C实现大概是这样#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint 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 1LL * t[i] * (n - 1 - i); } cout ans endl; return 0; }这里最容易被忽视的就是long long。GESP五级的测试数据里n可以到10^5t_i可以到10^4总等待时间最大能到10^5 * 10^4 * 10^5 ≈ 10^14int根本装不下。我批改过很多学生的代码因为没用long long丢分的比例相当高这个坑一定要提前避开。3. 经典模型一区间取舍中的代价最小化3.1 删掉最少的区间让剩余区间互不重叠如果说排队是“排序贪心”的代表那区间问题就是“贪心选择策略”的代表。GESP五级和CSP-J里都反复出现过这样一道题有若干个区间每个区间有起点和终点现在要删掉尽可能少的区间使得剩下的区间互不重叠不共享任何点问最少删几个。有些同学会先想到动态规划——确实如果是“最多保留多少个互不重叠的区间”可以按终点排序然后DP复杂度O(n^2)n一大就超时。但细心一想n如果到10^5DP就完全不可行了。正确思路是“看能保留多少而不是看删多少”。因为“删掉最少的”等于“保留最多的”。而“保留最多互不重叠区间”就是经典的区间调度问题贪心策略是按结束时间升序排序然后依次选择“与前一个已选区间不冲突且结束时间最早”的区间。为什么按结束时间排序直观理解结束时间越早的区间给后面的区间留出的空间越大后续能容纳的区间就越多。这就像开会订会议室哪个会先结束下一个会就能更早开始。3.2 这个题为什么也可以叫“损失最小化”你可能会问这不是“收益最大化”保留最多区间吗怎么变成损失最小化了这就是我前面说的“镜像关系”。当你看到题干写“删除最少区间”、“最小化删除代价”、“损失最小”这类字眼时不要慌先把它翻译成正向问题。比如“最少删几个区间让剩余的互不重叠”翻译过来就是“最多保留几个互不重叠的区间”然后用区间调度的贪心去做。考试里很多同学之所以栽在这个题上就是被“删除”这个词吓住了一直纠结“我该删哪个”而没想过“我该留哪个”。这里也提醒一句做贪心题题干里最扎眼的那个词往往不是解题方向反着思考往往有奇效。3.3 完整代码与实现细节直接给一版能过的代码#include bits/stdc.h using namespace std; struct Interval { int l, r; }; int main() { int n; cin n; vectorInterval a(n); for (int i 0; i n; i) { cin a[i].l a[i].r; } sort(a.begin(), a.end(), [](const Interval x, const Interval y) { return x.r y.r; // 按右端点升序 }); int cnt 0; int lastEnd -1e9; for (int i 0; i n; i) { if (a[i].l lastEnd) { cnt; lastEnd a[i].r; } } cout n - cnt endl; // 删掉的数量 总数 - 保留的数量 return 0; }注意事项有三个。第一区间“互不重叠”的定义题目里会说清楚有的题是闭区间“不能共享点”那判断条件就是a[i].l lastEnd严格大于有的题允许端点相接那判断条件是a[i].l lastEnd。GESP五级题目必须仔细读题目我自己遇到过学生代码完全一样就因为这个大于和大于等于的问题一个100一个0分。第二lastEnd的初始值要设成一个足够小的负数别用0。因为区间左端点可能是负数如果用0初始化所有左端点小于0的区间都会被错误地跳过。第三排序的lambda表达式里如果右端点相同理论上可以按左端点升序也可以不排。实测对结果没有影响但建议养成“右端点相同按左端点升序”的稳一点的习惯因为有些变体题需要左端点参与比较。4. 经典模型二过桥问题的最优代价4.1 题目描述与策略选择过桥问题也是GESP五级贪心题里的经典。描述通常是n个人要过一座桥每次最多只能过两个人且过桥时必须有手电筒过桥速度取决于两人中较慢的那个手电筒必须有人带回来。每个人过桥耗时已知问所有人全部过桥的最短时间。这个题我第一次接触时也很懵两个人一起过桥速度取慢的这明显是要把速度相近的人配对但还得有人送手电筒回来送回来的人不能太慢否则代价太大。这里就出现了典型的“两种候选策略”策略A最快的两个人轮流送手电筒。让最快的a和次快的b先过去a拿灯回来然后让最慢的两个人c和d一起过去b再拿灯回来。这个策略的代价是a b d ba、b过桥a回来c、d过桥b回来。策略B让最快的人全程当“搬运工”。a分别带c过去a回来再带d过去a回来。这个策略的代价是c a d a。哪种策略好不一定取决于c、d的耗时差异。所以贪心的核心是每一步都算两种策略的代价取较小的那个。4.2 两种情况的计算过程与比较用数学表达式写清楚。先把所有人耗时排序假设t[0] t[1] ... t[n-1]每次把最慢的两个人t[n-1]和t[n-2]送过桥有两种方案方案1快者护送式t[0] t[n-1] t[0] t[n-2] 2 * t[0] t[n-1] t[n-2]含义最快的人分别带最慢的人、次慢的人过桥每次最快的人都得回来。方案2小分队接力式t[0] t[1] t[n-1] t[1] t[0] 2 * t[1] t[n-1]含义最快的两个先过去最快回来最慢两个过去次快回来。每次比较这两个代价选小的。这个比较逻辑很多题解里只给了结论没有解释为什么两方案之间只需要比这两个。我是这么理解的最慢的那个人无论如何都得过桥他必须和一个同伴一起过而同伴大概率是最快的人但为了不让“送手电筒回来”的任务消耗一个慢速者要专门安排一个速度快的人守在对岸。如果把最慢的两人分别送最快的人得来回跑两次代价的“固定开销”是2*t[0]如果让最快的两人先过桥“埋伏”在对岸接应代价的固定开销多了一个t[1]但省下了第二次让t[0]单独往返的机会。4.3 n为奇数或偶数时的边界处理这个题还有个容易漏的边界当剩余人数为1、2、3时要单独处理。剩余1人直接过去代价t[0]排序后就是当前剩余的最小值剩余2人一起过去代价t[1]两人中较慢的剩余3人最快的两个先过去最快的回来带第三个人过去代价t[0] t[1] t[2]完整代码框架#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint t(n); for (int i 0; i n; i) cin t[i]; sort(t.begin(), t.end()); if (n 1) { cout t[0] endl; return 0; } if (n 2) { cout t[1] endl; return 0; } long long ans 0; int i n - 1; while (i 3) { // 方案1: 最快送 long long planA 2LL * t[0] t[i - 1] t[i]; // 方案2: 最快两个接应 long long planB 1LL * t[0] 2LL * t[1] t[i]; ans min(planA, planB); i - 2; } if (i 2) { ans t[0] t[1] t[2]; } else if (i 1) { ans t[1]; } cout ans endl; return 0; }这个题的“损失最小化”体现在哪里过桥总时间就是所有人的等待和通行代价总和。为了送手电筒总要有人付出额外的往返代价我们要做的就是让这个“额外的灯往返代价”最小化。考生最常见的错误是只掌握了一种策略就套到底结果遇到数据不同的测试点就挂实际上每次循环都要把两种策略都算一遍取min这才是真正的贪心。5. 贪心正确性的证明方法交换论证入门5.1 为什么必须证明贪心正确很多GESP五级考生有一个误区感觉贪心就是“猜个策略写个代码过了样例就交”。我见过太多人样例全过、提交零分原因就是贪心策略本身就是错的。在损失最小化这类逆向思维的题目里策略对不对更加隐蔽——样例往往是出题人特意构造的“适配”数据根本测不出策略漏洞。所以学贪心一定要学证明。五级考试不考证明题但备考的时候必须练证明思维。因为只有会证明你才能理解策略为何成立才能在考场那种紧张状态下判断自己该不该换策略。5.2 交换论证的基本套路排队问题的完整证明以排队接水为例我用交换论证法证明“按耗时短在前最优”。假设当前存在一个最优解中的相邻两人x和yx在y前且t[x] t[y]。考虑交换x和y其他所有人的相对位置不变。交换前x和y两个人对总等待时间的贡献x的等待不受影响但y要多等t[x]问题里所有人等待时间都累加所以这一段的贡献包含y多出的t[x]。交换后x要多等t[y]。交换前与交换后的总代价差交换前总代价 - 交换后总代价 t[x] - t[y] 0说明交换后的总代价更小这与“当前是最优解”矛盾。所以任意最优解中不可能出现“耗时长的排在耗时短的之前”这种情况排序后唯一可能的就是按耗时升序。这个证明的核心是“相邻逆序交换只会让结果更好”只要所有逆序都能被消除且不劣化答案那么完全有序的方案就是最优的。这一招在几乎所有的“排序型”贪心证明里都能用强烈建议你们练熟。5.3 反例思维什么时候贪心会翻车说句实话贪心算法不是万能的。GESP五级虽然贪心考得多但绝对不是所有题都能贪心。比如0-1背包问题、部分背包可以贪心但0-1背包不可以很多五级考生就是因为把“物品可以分割”误当成“不可分割”套了贪心就翻车。怎么判断一个题能不能用贪心核心标准是局部最优选择能否保证全局最优。具体来说你可以尝试找一个反例。如果构造了半天都构造不出来而且你能用交换论证证明策略的正确性那基本能放心用贪心如果一构造就出来了比如0-1背包“性价比最高优先”就能找到反例那就要考虑DP或者别的算法。这里我分享一个我备考时特别喜欢用的“反例自查法”假设你已经想好一个贪心策略然后故意构造一组数据让“第一步看起来最优的选择”在后续造成更大的代价看看是否会导致全局不是最优。如果会说明贪心不成立。这个方法很土但真的有效尤其对付损失最小化这类逆向题。6. GESP五级考试中的常见坑与排查清单6.1 坑点一排序依据写错或方向写反这是损失最小化题目的第一大坑。有的题目让你把“代价”作为排序依据有的让你把“截止时间”作为依据有的让你把“耗时”作为依据。一个很实用的经验先看目标函数里加权的是什么被加权的一定是关键排序依据。比如排队接水被加权的是每个人的耗时后面等的人数所以排序依据是耗时。活动安排被加权的是结束时间所以排序依据是结束时间。任务延误最小化被加权的是截止时间和延误代价的综合通常要先按截止时间排序。6.2 坑点二int溢出和long long前面已经强调过一次这里再次强调因为真的太重要了。GESP五级数据范围往往给到10^5级别代价累加很容易突破int上限。我的习惯是所有累加变量直接用long long排序的 comparator 里如果涉及乘法也先转long long再算。虽然多敲了几个字母但能帮你避免最冤的丢分。6.3 坑点三区间端点重合到底算不算重叠这个坑我在第3节说过但展开讲一下不同题目里的差异如果题目说“两个区间不能有公共点”那端点重合就算重叠判断用。如果题目说“区间可以首尾相接”那端点重合不算重叠判断用。有些题目比如区间覆盖变体判定条件更怪必须以题目为准绝不能想当然。考场上判断这个的最快方法看样例。样例里通常会包含一组恰好端点相接的数据你拿代码跑一遍如果和样例一致说明判断条件对了否则赶紧改。6.4 考场上验证贪心的三个小技巧第一构造极端数据。比如所有人都一样耗时所有人都一个区间最大数据范围边界值。极端数据能快速暴露排序和比较逻辑的bug。第二写一个暴力版对拍。有些选手觉得对拍是竞赛才用五级不过是个等级考试没必要。但我告诉你们对拍是验证贪心最可靠的手段。用n8的随机小数据暴力枚举所有方案求最优值和贪心结果比对跑几百组随机数据正确性基本就有保证了。C写暴力枚举可以用next_permutation非常方便。第三用手算“人工单调性测试”。拿一组数据故意把顺序打乱按你的策略排序手算几步看代价变化是否符合预期。这个方法慢但对理解题目非常有帮助。7. 备考建议与题型清单最后给大家梳理一份GESP五级贪心部分的复习清单按优先级排列优先级题型/知识点建议掌握的代码能力必考排序类贪心排队、调度sort自定义比较器、相邻交换证明必考区间类贪心活动安排、区间覆盖右端点排序、选择逻辑高频过桥问题两种策略取min、边界人数组处理高频哈夫曼编码合并果子最小代价优先队列 priority_queue中频反悔贪心后悔堆优先队列 堆顶替换中频单调栈/单调队列相关贪心栈/队列维护候选集合哈夫曼编码这个题型我没展开但它绝对是GESP五级“代价最小化”的一员大将——合并n堆果子每次合并代价是两堆数量之和问最小总代价。这个题的标准做法是每次合并最小的两堆用优先队列维护。它和排队接水一样都是“局部代价最小全局也最优”的典型值得你们单独花时间练。再说点备考节奏上的建议。如果你离考试还有一个月贪心部分我建议这样分配时间第一周把上面提到的四类题型全部手写一遍不求快但求每一题都能把“为什么选这个策略”用交换论证或者反例思维说清楚。第二周刷GESP五级历年真题里的贪心题刷的时候有意练习“读题翻译”看到最小化、最大化主动把它转成自己熟悉的模型。第三周做模拟卷严格按考场时间限时重点练“10分钟想不出策略就换思路”的应试节奏。最后几天复习自己的错题本尤其是排序方向和边界条件。说句掏心窝的话GESP五级并不难难的是你以为自己会了。贪心算法尤其如此——它代码短、思想简单但正因为简单很多人不重视证明和反例一到变式题就露怯。损失最小化这类题更是把“逆向思维”拉满了你只有把正向和反向都打通才能在考场上真正游刃有余。根据我个人带学生刷题的经验每届五级考生里能把贪心题稳定拿满分的基本上都有一个共同习惯做完题之后会强行给自己讲一遍“这题我为什么这么贪心是对的”。这个习惯看起来很傻但它逼着你把直觉变成逻辑把“猜策略”变成“推策略”。如果你能坚持到考试前贪心这一块就是稳的。 
长河君 · 2026/9/8 9:14:00 · 阅读 1.2k GESP五级贪心算法：损失最小化模型与排序策略全解析
GESP五级通关秘籍贪心算法中的“损失最小化”到底怎么破每年GESP五级考完总有一批学生出来就吐槽“贪心我也学了题也刷了怎么一上考场还是不知道先排哪个序、选哪个局部最优”尤其是碰到“代价最小化”“损失最小化”这种表述的题目很多人第一反应就是懵——因为教材上讲的贪心基本都是“收益最大化”比如最大价值、最长区间、最多活动这类一旦题干反过来让你最小化代价、最小化损失很多人就开始凭感觉乱试了。其实“损失最小化”是贪心算法里非常经典的一类模型它跟“收益最大化”在思路上完全是镜像关系。GESP五级的真题和模拟题里排队接水、删区间使剩余区间不重叠、多人过桥这些题目本质上都是损失最小化问题。把这一块彻底吃透五级考试的贪心部分基本上就能拿稳了。这篇文章我会从概念讲到证明从代码讲到考场避坑争取让你看完就能直接上手做题。1. 先把概念说透损失最小化到底在解决什么问题1.1 从“赚到的”和“花掉的”两个角度理解贪心先说个生活化的类比。假设你一天要做5件事每件事耗时不同你希望“一天结束前完成的任务数量最多”这时候你要做的贪心是什么优先做耗时短的——这是经典的“活动安排”思路。但如果反过来每件事都固定有截止时间一旦超时就罚钱你希望“被罚的钱最少”这时候你优先做哪件肯定不是无脑做耗时短的而是要综合考虑截止时间和耗时。这就是损失最小化和收益最大化的本质区别收益最大化问题里答案往往藏在“先做性价比最高的”而损失最小化问题里你要在“当前损失”和“未来损失”之间做权衡贪心策略往往体现在“先把会造成最大损失的解决掉”或者“把代价最小的优先处理”。再回到GESP五级的真题场景。五级考试里最常出现的损失最小化题目就是“排队接水”有n个人排队接水第i个人接水需要t_i分钟每个人等待的时间都要算进总代价问所有人等待时间总和最小怎么排队。这道题几乎所有教材都会讲解法是“按接水时间从短到长排队”。但你有没有想过为什么要这样排随机选两个人A和B接水时间分别是a和b且a b。如果A排在B前面B的等待时间就要多a分钟如果B排在A前面A的等待时间就要多b分钟。前者比后者多等a - b分钟。所以要总等待时间最小必然是把耗时短的那个人排前面。这个“交换两个相邻元素看差异”的方法就是贪心证明里最常用的交换论证法后面第五节我会详细展开。1.2 损失最小化其实是收益最大化的“镜像”很多同学没有意识到一个问题里的“损失”换个说法可能就变成了收益。举例来说还是排队接水如果问你“所有人等待时间总和最小”这是损失最小化。但如果你把问题改成“假设每个人都有一个固定的价值问怎么排队让总价值最大化”它就可能变成一个不同的贪心——这时候就不是只看时间了要看“价值/时间”的比值。GESP五级题目里经常会用这种“镜像关系”来迷惑考生。同一个模型换个说法贪心策略完全不同。所以拿到题目第一步永远不是写代码而是先问自己三个问题这个题的目标到底是最大化什么还是最小化什么如果我选择某个方案付出的代价是什么这个代价跟哪些因素有关排序依据是什么把这三个问题想清楚贪心题就成功了一半。1.3 什么样的题会用到“代价最小化”模型我总结了一下GESP五级以及同类考试里常见的损失最小化题型大致有这几类题目类型典型描述贪心策略排队问题n个人排队每人服务时间不同总等待时间最小时间短的先服务区间取舍删掉最少的区间使剩余区间互不重叠按结束时间排序贪心任务调度任务有截止时间和延误代价总延误最小按截止时间排序或按代价大小处理过桥问题多人过桥一次最多两人需持灯往返总时间最短分情况比较两种策略最小化删除代价数组删元素使满足某种性质删除代价最小通常用单调栈或优先队列你注意看前三类在GESP真题里出现频率非常高后面我会挑最典型的两个模型拆开讲透代码也给到可以直接背的程度。2. 排序贪心最核心的武器一次讲明白2.1 排队问题等待总时间最小化这是GESP五级贪心里的“入门题”也是很多学校信息学社团的第一道贪心题。题目描述基本是这样的n个人排队接水第i个人需要t_i分钟每个人的等待时间是从他开始排队到他接到水的总时长问怎么排队能让所有人等待时间总和最小。直接上结论按t从小到大排序。为什么不对所有人统一按时间长的先因为“等待时间的总和”里越靠前的人影响的人越多。第1个人只影响自己第2个人影响自己和后面所有人第n个人影响所有人。如果让一个耗时巨长的人排前面他后面每个人都要白白多等那么久这个代价是乘法级别的增长。用严格一点的方式表述如果排队顺序是p_1, p_2, ..., p_n那么总等待时间是T t[p_1] * (n - 1) t[p_2] * (n - 2) ... t[p_n] * 0看到没有第k个位置的人他的耗时会被乘以他后面的人数。所以要让总时间小就必须让耗时短的人尽量往后排不对——注意这里是乘以“后面的人数”也就是说越靠前的人权重越大n-1最大所以耗时越短的人应该放在权重大的位置。这就是为什么按耗时升序排。2.2 排序方向的决定方法三种常见错误要避免这里我要专门说一下排序方向因为这是损失最小化问题里最容易翻车的点。GESP五级考生做错排队题九成的原因是排序方向搞反了。我见过三种典型错误第一种想当然觉得“时间长的先走后面的人等的时间就少”实际上时间长的先走后面每个人都要被这个长耗时拖累总等待时间反而大。第二种把公式记成乘以“前面的人数”然后得出按耗时降序排的结论这种情况下你至少证明过程是严谨的只是原题看错了——注意有的题目问“总等待时间”有的题目问“总完成时间”两者排序方向一样都是升序但如果问的是“平均等待时间”也是升序千万不要被换了个说法带偏。第三种把“等待时间”等同于“服务时间总和”。等待时间不是累加每个人耗时那么简单而是对每个人而言“他到达后到开始被服务之间的时间”排队接水场景中第i个人的等待时间等于排在他前面所有人的耗时之和不是他自己的耗时。那排序方向到底怎么定我给你们一个通用方法假设两个相邻元素x和y交换它们俩的位置不影响其他元素分别算出“x在y前”和“y在x前”两种方案的代价比较大小取更小的方案成立的不等式就是排序依据。这招叫相邻交换法几乎能解决所有排序类贪心。2.3 代码实现与long long陷阱排队接水这类题的代码很短C实现大概是这样#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint 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 1LL * t[i] * (n - 1 - i); } cout ans endl; return 0; }这里最容易被忽视的就是long long。GESP五级的测试数据里n可以到10^5t_i可以到10^4总等待时间最大能到10^5 * 10^4 * 10^5 ≈ 10^14int根本装不下。我批改过很多学生的代码因为没用long long丢分的比例相当高这个坑一定要提前避开。3. 经典模型一区间取舍中的代价最小化3.1 删掉最少的区间让剩余区间互不重叠如果说排队是“排序贪心”的代表那区间问题就是“贪心选择策略”的代表。GESP五级和CSP-J里都反复出现过这样一道题有若干个区间每个区间有起点和终点现在要删掉尽可能少的区间使得剩下的区间互不重叠不共享任何点问最少删几个。有些同学会先想到动态规划——确实如果是“最多保留多少个互不重叠的区间”可以按终点排序然后DP复杂度O(n^2)n一大就超时。但细心一想n如果到10^5DP就完全不可行了。正确思路是“看能保留多少而不是看删多少”。因为“删掉最少的”等于“保留最多的”。而“保留最多互不重叠区间”就是经典的区间调度问题贪心策略是按结束时间升序排序然后依次选择“与前一个已选区间不冲突且结束时间最早”的区间。为什么按结束时间排序直观理解结束时间越早的区间给后面的区间留出的空间越大后续能容纳的区间就越多。这就像开会订会议室哪个会先结束下一个会就能更早开始。3.2 这个题为什么也可以叫“损失最小化”你可能会问这不是“收益最大化”保留最多区间吗怎么变成损失最小化了这就是我前面说的“镜像关系”。当你看到题干写“删除最少区间”、“最小化删除代价”、“损失最小”这类字眼时不要慌先把它翻译成正向问题。比如“最少删几个区间让剩余的互不重叠”翻译过来就是“最多保留几个互不重叠的区间”然后用区间调度的贪心去做。考试里很多同学之所以栽在这个题上就是被“删除”这个词吓住了一直纠结“我该删哪个”而没想过“我该留哪个”。这里也提醒一句做贪心题题干里最扎眼的那个词往往不是解题方向反着思考往往有奇效。3.3 完整代码与实现细节直接给一版能过的代码#include bits/stdc.h using namespace std; struct Interval { int l, r; }; int main() { int n; cin n; vectorInterval a(n); for (int i 0; i n; i) { cin a[i].l a[i].r; } sort(a.begin(), a.end(), [](const Interval x, const Interval y) { return x.r y.r; // 按右端点升序 }); int cnt 0; int lastEnd -1e9; for (int i 0; i n; i) { if (a[i].l lastEnd) { cnt; lastEnd a[i].r; } } cout n - cnt endl; // 删掉的数量 总数 - 保留的数量 return 0; }注意事项有三个。第一区间“互不重叠”的定义题目里会说清楚有的题是闭区间“不能共享点”那判断条件就是a[i].l lastEnd严格大于有的题允许端点相接那判断条件是a[i].l lastEnd。GESP五级题目必须仔细读题目我自己遇到过学生代码完全一样就因为这个大于和大于等于的问题一个100一个0分。第二lastEnd的初始值要设成一个足够小的负数别用0。因为区间左端点可能是负数如果用0初始化所有左端点小于0的区间都会被错误地跳过。第三排序的lambda表达式里如果右端点相同理论上可以按左端点升序也可以不排。实测对结果没有影响但建议养成“右端点相同按左端点升序”的稳一点的习惯因为有些变体题需要左端点参与比较。4. 经典模型二过桥问题的最优代价4.1 题目描述与策略选择过桥问题也是GESP五级贪心题里的经典。描述通常是n个人要过一座桥每次最多只能过两个人且过桥时必须有手电筒过桥速度取决于两人中较慢的那个手电筒必须有人带回来。每个人过桥耗时已知问所有人全部过桥的最短时间。这个题我第一次接触时也很懵两个人一起过桥速度取慢的这明显是要把速度相近的人配对但还得有人送手电筒回来送回来的人不能太慢否则代价太大。这里就出现了典型的“两种候选策略”策略A最快的两个人轮流送手电筒。让最快的a和次快的b先过去a拿灯回来然后让最慢的两个人c和d一起过去b再拿灯回来。这个策略的代价是a b d ba、b过桥a回来c、d过桥b回来。策略B让最快的人全程当“搬运工”。a分别带c过去a回来再带d过去a回来。这个策略的代价是c a d a。哪种策略好不一定取决于c、d的耗时差异。所以贪心的核心是每一步都算两种策略的代价取较小的那个。4.2 两种情况的计算过程与比较用数学表达式写清楚。先把所有人耗时排序假设t[0] t[1] ... t[n-1]每次把最慢的两个人t[n-1]和t[n-2]送过桥有两种方案方案1快者护送式t[0] t[n-1] t[0] t[n-2] 2 * t[0] t[n-1] t[n-2]含义最快的人分别带最慢的人、次慢的人过桥每次最快的人都得回来。方案2小分队接力式t[0] t[1] t[n-1] t[1] t[0] 2 * t[1] t[n-1]含义最快的两个先过去最快回来最慢两个过去次快回来。每次比较这两个代价选小的。这个比较逻辑很多题解里只给了结论没有解释为什么两方案之间只需要比这两个。我是这么理解的最慢的那个人无论如何都得过桥他必须和一个同伴一起过而同伴大概率是最快的人但为了不让“送手电筒回来”的任务消耗一个慢速者要专门安排一个速度快的人守在对岸。如果把最慢的两人分别送最快的人得来回跑两次代价的“固定开销”是2*t[0]如果让最快的两人先过桥“埋伏”在对岸接应代价的固定开销多了一个t[1]但省下了第二次让t[0]单独往返的机会。4.3 n为奇数或偶数时的边界处理这个题还有个容易漏的边界当剩余人数为1、2、3时要单独处理。剩余1人直接过去代价t[0]排序后就是当前剩余的最小值剩余2人一起过去代价t[1]两人中较慢的剩余3人最快的两个先过去最快的回来带第三个人过去代价t[0] t[1] t[2]完整代码框架#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint t(n); for (int i 0; i n; i) cin t[i]; sort(t.begin(), t.end()); if (n 1) { cout t[0] endl; return 0; } if (n 2) { cout t[1] endl; return 0; } long long ans 0; int i n - 1; while (i 3) { // 方案1: 最快送 long long planA 2LL * t[0] t[i - 1] t[i]; // 方案2: 最快两个接应 long long planB 1LL * t[0] 2LL * t[1] t[i]; ans min(planA, planB); i - 2; } if (i 2) { ans t[0] t[1] t[2]; } else if (i 1) { ans t[1]; } cout ans endl; return 0; }这个题的“损失最小化”体现在哪里过桥总时间就是所有人的等待和通行代价总和。为了送手电筒总要有人付出额外的往返代价我们要做的就是让这个“额外的灯往返代价”最小化。考生最常见的错误是只掌握了一种策略就套到底结果遇到数据不同的测试点就挂实际上每次循环都要把两种策略都算一遍取min这才是真正的贪心。5. 贪心正确性的证明方法交换论证入门5.1 为什么必须证明贪心正确很多GESP五级考生有一个误区感觉贪心就是“猜个策略写个代码过了样例就交”。我见过太多人样例全过、提交零分原因就是贪心策略本身就是错的。在损失最小化这类逆向思维的题目里策略对不对更加隐蔽——样例往往是出题人特意构造的“适配”数据根本测不出策略漏洞。所以学贪心一定要学证明。五级考试不考证明题但备考的时候必须练证明思维。因为只有会证明你才能理解策略为何成立才能在考场那种紧张状态下判断自己该不该换策略。5.2 交换论证的基本套路排队问题的完整证明以排队接水为例我用交换论证法证明“按耗时短在前最优”。假设当前存在一个最优解中的相邻两人x和yx在y前且t[x] t[y]。考虑交换x和y其他所有人的相对位置不变。交换前x和y两个人对总等待时间的贡献x的等待不受影响但y要多等t[x]问题里所有人等待时间都累加所以这一段的贡献包含y多出的t[x]。交换后x要多等t[y]。交换前与交换后的总代价差交换前总代价 - 交换后总代价 t[x] - t[y] 0说明交换后的总代价更小这与“当前是最优解”矛盾。所以任意最优解中不可能出现“耗时长的排在耗时短的之前”这种情况排序后唯一可能的就是按耗时升序。这个证明的核心是“相邻逆序交换只会让结果更好”只要所有逆序都能被消除且不劣化答案那么完全有序的方案就是最优的。这一招在几乎所有的“排序型”贪心证明里都能用强烈建议你们练熟。5.3 反例思维什么时候贪心会翻车说句实话贪心算法不是万能的。GESP五级虽然贪心考得多但绝对不是所有题都能贪心。比如0-1背包问题、部分背包可以贪心但0-1背包不可以很多五级考生就是因为把“物品可以分割”误当成“不可分割”套了贪心就翻车。怎么判断一个题能不能用贪心核心标准是局部最优选择能否保证全局最优。具体来说你可以尝试找一个反例。如果构造了半天都构造不出来而且你能用交换论证证明策略的正确性那基本能放心用贪心如果一构造就出来了比如0-1背包“性价比最高优先”就能找到反例那就要考虑DP或者别的算法。这里我分享一个我备考时特别喜欢用的“反例自查法”假设你已经想好一个贪心策略然后故意构造一组数据让“第一步看起来最优的选择”在后续造成更大的代价看看是否会导致全局不是最优。如果会说明贪心不成立。这个方法很土但真的有效尤其对付损失最小化这类逆向题。6. GESP五级考试中的常见坑与排查清单6.1 坑点一排序依据写错或方向写反这是损失最小化题目的第一大坑。有的题目让你把“代价”作为排序依据有的让你把“截止时间”作为依据有的让你把“耗时”作为依据。一个很实用的经验先看目标函数里加权的是什么被加权的一定是关键排序依据。比如排队接水被加权的是每个人的耗时后面等的人数所以排序依据是耗时。活动安排被加权的是结束时间所以排序依据是结束时间。任务延误最小化被加权的是截止时间和延误代价的综合通常要先按截止时间排序。6.2 坑点二int溢出和long long前面已经强调过一次这里再次强调因为真的太重要了。GESP五级数据范围往往给到10^5级别代价累加很容易突破int上限。我的习惯是所有累加变量直接用long long排序的 comparator 里如果涉及乘法也先转long long再算。虽然多敲了几个字母但能帮你避免最冤的丢分。6.3 坑点三区间端点重合到底算不算重叠这个坑我在第3节说过但展开讲一下不同题目里的差异如果题目说“两个区间不能有公共点”那端点重合就算重叠判断用。如果题目说“区间可以首尾相接”那端点重合不算重叠判断用。有些题目比如区间覆盖变体判定条件更怪必须以题目为准绝不能想当然。考场上判断这个的最快方法看样例。样例里通常会包含一组恰好端点相接的数据你拿代码跑一遍如果和样例一致说明判断条件对了否则赶紧改。6.4 考场上验证贪心的三个小技巧第一构造极端数据。比如所有人都一样耗时所有人都一个区间最大数据范围边界值。极端数据能快速暴露排序和比较逻辑的bug。第二写一个暴力版对拍。有些选手觉得对拍是竞赛才用五级不过是个等级考试没必要。但我告诉你们对拍是验证贪心最可靠的手段。用n8的随机小数据暴力枚举所有方案求最优值和贪心结果比对跑几百组随机数据正确性基本就有保证了。C写暴力枚举可以用next_permutation非常方便。第三用手算“人工单调性测试”。拿一组数据故意把顺序打乱按你的策略排序手算几步看代价变化是否符合预期。这个方法慢但对理解题目非常有帮助。7. 备考建议与题型清单最后给大家梳理一份GESP五级贪心部分的复习清单按优先级排列优先级题型/知识点建议掌握的代码能力必考排序类贪心排队、调度sort自定义比较器、相邻交换证明必考区间类贪心活动安排、区间覆盖右端点排序、选择逻辑高频过桥问题两种策略取min、边界人数组处理高频哈夫曼编码合并果子最小代价优先队列 priority_queue中频反悔贪心后悔堆优先队列 堆顶替换中频单调栈/单调队列相关贪心栈/队列维护候选集合哈夫曼编码这个题型我没展开但它绝对是GESP五级“代价最小化”的一员大将——合并n堆果子每次合并代价是两堆数量之和问最小总代价。这个题的标准做法是每次合并最小的两堆用优先队列维护。它和排队接水一样都是“局部代价最小全局也最优”的典型值得你们单独花时间练。再说点备考节奏上的建议。如果你离考试还有一个月贪心部分我建议这样分配时间第一周把上面提到的四类题型全部手写一遍不求快但求每一题都能把“为什么选这个策略”用交换论证或者反例思维说清楚。第二周刷GESP五级历年真题里的贪心题刷的时候有意练习“读题翻译”看到最小化、最大化主动把它转成自己熟悉的模型。第三周做模拟卷严格按考场时间限时重点练“10分钟想不出策略就换思路”的应试节奏。最后几天复习自己的错题本尤其是排序方向和边界条件。说句掏心窝的话GESP五级并不难难的是你以为自己会了。贪心算法尤其如此——它代码短、思想简单但正因为简单很多人不重视证明和反例一到变式题就露怯。损失最小化这类题更是把“逆向思维”拉满了你只有把正向和反向都打通才能在考场上真正游刃有余。根据我个人带学生刷题的经验每届五级考生里能把贪心题稳定拿满分的基本上都有一个共同习惯做完题之后会强行给自己讲一遍“这题我为什么这么贪心是对的”。这个习惯看起来很傻但它逼着你把直觉变成逻辑把“猜策略”变成“推策略”。如果你能坚持到考试前贪心这一块就是稳的。