企业官网建设流程全解析

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. 这个题的目标到底是最大化什么，还是最小化什么？
2. 如果我选择某个方案，付出的代价是什么？
3. 这个代价跟哪些因素有关，排序依据是什么？

把这三个问题想清楚，贪心题就成功了一半。

1.3 什么样的题会用到“代价最小化”模型

我总结了一下GESP五级以及同类考试里，常见的损失最小化题型大致有这几类：

你注意看，前三类在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; vector<int> 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^5，t_i可以到10^4，总等待时间最大能到10^5 * 10^4 * 10^5 ≈ 10^14，int根本装不下。我批改过很多学生的代码，因为没用long long丢分的比例相当高，这个坑一定要提前避开。

3. 经典模型一：区间取舍中的代价最小化

3.1 删掉最少的区间，让剩余区间互不重叠

如果说排队是“排序贪心”的代表，那区间问题就是“贪心选择策略”的代表。GESP五级和CSP-J里都反复出现过这样一道题：有若干个区间，每个区间有起点和终点，现在要删掉尽可能少的区间，使得剩下的区间互不重叠（不共享任何点），问最少删几个。

有些同学会先想到动态规划——确实，如果是“最多保留多少个互不重叠的区间”，可以按终点排序然后DP，复杂度O(n^2)，n一大就超时。但细心一想，n如果到10^5，DP就完全不可行了。

正确思路是“看能保留多少，而不是看删多少”。因为“删掉最少的”等于“保留最多的”。而“保留最多互不重叠区间”就是经典的区间调度问题，贪心策略是按结束时间升序排序，然后依次选择“与前一个已选区间不冲突且结束时间最早”的区间。

为什么按结束时间排序？直观理解：结束时间越早的区间，给后面的区间留出的空间越大，后续能容纳的区间就越多。这就像开会订会议室，哪个会先结束，下一个会就能更早开始。

3.2 这个题为什么也可以叫“损失最小化”

你可能会问：这不是“收益最大化”（保留最多区间）吗？怎么变成损失最小化了？

这就是我前面说的“镜像关系”。当你看到题干写“删除最少区间”、“最小化删除代价”、“损失最小”这类字眼时，不要慌，先把它翻译成正向问题。比如“最少删几个区间让剩余的互不重叠”，翻译过来就是“最多保留几个互不重叠的区间”，然后用区间调度的贪心去做。

考试里很多同学之所以栽在这个题上，就是被“删除”这个词吓住了，一直纠结“我该删哪个”，而没想过“我该留哪个”。这里也提醒一句：做贪心题，题干里最扎眼的那个词往往不是解题方向，反着思考往往有奇效。

3.3 完整代码与实现细节

直接给一版能过的代码：

#include <bits/stdc++.h> using namespace std; struct Interval { int l, r; }; int main() { int n; cin >> n; vector<Interval> 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 + b（a、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; vector<int> 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和y，x在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。

第二，写一个暴力版对拍。有些选手觉得对拍是竞赛才用，五级不过是个等级考试没必要。但我告诉你们，对拍是验证贪心最可靠的手段。用n<=8的随机小数据，暴力枚举所有方案求最优值，和贪心结果比对，跑几百组随机数据，正确性基本就有保证了。C++写暴力枚举可以用next_permutation，非常方便。

第三，用手算“人工单调性测试”。拿一组数据，故意把顺序打乱，按你的策略排序，手算几步看代价变化是否符合预期。这个方法慢，但对理解题目非常有帮助。

7. 备考建议与题型清单

最后给大家梳理一份GESP五级贪心部分的复习清单，按优先级排列：

哈夫曼编码这个题型我没展开，但它绝对是GESP五级“代价最小化”的一员大将——合并n堆果子，每次合并代价是两堆数量之和，问最小总代价。这个题的标准做法是每次合并最小的两堆，用优先队列维护。它和排队接水一样，都是“局部代价最小，全局也最优”的典型，值得你们单独花时间练。

再说点备考节奏上的建议。如果你离考试还有一个月，贪心部分我建议这样分配时间：

第一周，把上面提到的四类题型全部手写一遍，不求快，但求每一题都能把“为什么选这个策略”用交换论证或者反例思维说清楚。第二周，刷GESP五级历年真题里的贪心题，刷的时候有意练习“读题翻译”：看到最小化、最大化，主动把它转成自己熟悉的模型。第三周，做模拟卷，严格按考场时间限时，重点练“10分钟想不出策略就换思路”的应试节奏。最后几天，复习自己的错题本，尤其是排序方向和边界条件。

说句掏心窝的话，GESP五级并不难，难的是你以为自己会了。贪心算法尤其如此——它代码短、思想简单，但正因为简单，很多人不重视证明和反例，一到变式题就露怯。损失最小化这类题更是把“逆向思维”拉满了，你只有把正向和反向都打通，才能在考场上真正游刃有余。

根据我个人带学生刷题的经验，每届五级考生里，能把贪心题稳定拿满分的，基本上都有一个共同习惯：做完题之后，会强行给自己讲一遍“这题我为什么这么贪心是对的”。这个习惯看起来很傻，但它逼着你把直觉变成逻辑，把“猜策略”变成“推策略”。如果你能坚持到考试前，贪心这一块就是稳的。