第 48 章贪心算法——局部最优的智慧

🏗️ 前情回顾：第 45 和 46 章你学会了二分——在有序空间中高效定位。二分依赖"单调性"。但现实生活中，很多问题没有全局的单调结构，却有另一种朴素智慧：每走一步，都选当下看起来最好的那个选项。这就是贪心算法，它简单、快速，但也容易被"眼前利益"欺骗。

🎯 本章目标

学完这一章，你能：

理解贪心算法的核心思想：每一步选局部最优
区分贪心和 DP 的适用场景
掌握经典贪心：找零钱、最优装载、活动选择、排队接水
学会贪心的证明思路（反证法、归纳法）
识别贪心的"陷阱"——局部最优 ≠ 全局最优
知道哪些经典问题贪心有效、哪些反例说明贪心失效

📖 故事引入

你去吃自助餐，肚子容量有限。桌上摆着各种食物：龙虾、牛排、蔬菜沙拉、小蛋糕……你该怎么吃才能"最划算"？

如果每样食物的"满足感"和"占用肚子空间"不同，这就成了著名的背包问题。直觉告诉你：先吃单价贵的（比如龙虾）——这就是贪心。

但等一下：如果龙虾虽然贵，但非常占肚子，吃了它就没空间吃别的了……或许吃 3 份牛排比 1 份龙虾更划算？

这就是贪心的魅力与困境：每步选最好的，不一定最终最好。

再看另一个场景：你面前有 10 个任务，每个有开始和结束时间。你只有一个 CPU，同一时间只能做一个任务。怎么安排能让完成的任务数最多？

直觉：每次都选最早结束的任务，这样就能腾出时间做更多任务。这个贪心恰好是正确的！

结论：贪心不是万能钥匙，但在它适用的场景里，没有比它更简单高效的武器。

🧱 知识讲解

48.1 贪心思想：每步选最好的

贪心算法的框架极其简单：

while (还有选择) {
    在所有可选方案中，选一个"当前最优"的
    做出这个选择
    更新可选集合
}

没有回溯，没有记忆化，一条路走到黑。贪心做出的选择从来不会撤销。

48.2 贪心 vs DP

	贪心	动态规划（DP）
决策	每步选局部最优，不回头	考虑所有可能，用之前结果推现在
速度	很快（通常 O(n log n)）	较慢（O(n²) 或更高）
正确性	必须证明，不一定对	只要状态和转移对，就一定对
空间	O(1) 或 O(n)	通常 O(n) 或 O(n²)
问题特征	贪心选择性质 + 最优子结构	最优子结构 + 重叠子问题

🧠 贪心是 DP 的特例——当 DP 的每一步最优选择恰好依赖于贪心策略时，DP 退化为贪心。

48.3 经典贪心一：找零钱

问题：用最少的硬币凑出金额 M。硬币面值为 {1, 5, 10, 20, 50, 100}。

贪心策略：每次选面值最大且不超过剩余金额的硬币。

cpp

int coins[] = {100, 50, 20, 10, 5, 1};
int m, cnt = 0;
cin >> m;
for (int c : coins) {
    cnt += m / c;      // 尽量用大面值
    m %= c;            // 剩下的金额
}
cout << cnt;

这个贪心正确吗？ 对于 {1,5,10,20,50,100} 这套面值，是正确的（人民币面值就是这么设计的）。但如果面值变成 {1, 3, 4}，凑 6：贪心会选 4+1+1（3 枚），但最优是 3+3（2 枚）。贪心失效了！

⚠️ 找零钱问题的贪心是否有效，取决于硬币面值的性质。一般情况需要用 DP。

48.4 经典贪心二：最优装载

问题：有 n 个物品，重量 w₁...wₙ。一艘船载重为 C。物品不可拆分。问最多能装几件？

贪心策略：按重量从小到大排序，先装轻的，装到装不下为止。

cpp

sort(w, w + n);     // 从小到大
int cnt = 0, sum = 0;
for (int i = 0; i < n; i++) {
    if (sum + w[i] <= C) {
        sum += w[i];
        cnt++;
    } else break;
}
cout << cnt;

这个贪心正确吗？ 是的。证明很简单：如果有最优解没选某个最轻的物品而选了一个更重的，把它换成更轻的，重量不增加，件数不减。

48.5 经典贪心三：活动选择（区间调度）

问题：n 个活动，第 i 个开始于 sᵢ，结束于 fᵢ。同一时间只能做一个活动。问最多选几个？

贪心策略：按结束时间从早到晚排序，每次选最早结束且和已选不冲突的。

cpp

struct Act { int s, f; };
Act a[1005];

bool cmp(Act x, Act y) { return x.f < y.f; }

sort(a, a + n, cmp);
int cnt = 1;
int lastEnd = a[0].f;
for (int i = 1; i < n; i++) {
    if (a[i].s >= lastEnd) {   // 不冲突
        cnt++;
        lastEnd = a[i].f;
    }
}
cout << cnt;

🔍 为什么按结束时间而不是开始时间？因为早结束的活动给后面留出更多空间。选"最不贪"的那个（最早结束），反而是最聪明的。

正确性证明（反证法）：假设最优解的第一个活动和贪心选的（最早结束的活动）不同——那把最优解的第一个换成最早结束的，不会冲突，且活动数不变或更多。

48.6 经典贪心四：排队接水

问题：n 个人排队接水，第 i 个人需要 tᵢ 时间。所有人的等待时间总和 = 每个人开始接水之前等待的时间之和。求最小的总等待时间。

贪心策略：接水快的人排前面（按 tᵢ 升序排列）。

cpp

sort(t, t + n);        // 接水时间从小到大
long long wait = 0, total = 0;
for (int i = 0; i < n; i++) {
    total += wait;     // 当前这个人等的时间
    wait += t[i];      // 下一个人要多等 t[i]
}
cout << total;

这为什么对？交换法：如果存在 i<j 但 tᵢ > tⱼ，交换他们能减少总等待时间。

48.7 贪心的陷阱：局部最优 ≠ 全局最优

经典的反例帮你建立对贪心的"警惕感"：

反例 1 — 硬币找零（面值 {1, 3, 4}，凑 6）：贪心：4+1+1=3 枚，最优：3+3=2 枚。

反例 2 — 0-1 背包（贪心价值密度）：背包容量 10。物品 A：重量 6，价值 7（密度 1.17）；物品 B：重量 5，价值 5（密度 1.0）；物品 C：重量 5，价值 5（密度 1.0）。贪心先拿 A（密度最高），剩 4 容量拿不了 B 和 C，总价值 7。最优：拿 B 和 C，总价值 10。

反例 3 — 最大子段和：不能贪心——从正数开始捡不一定对，因为后面可能有大负数。需要 DP 或分治。

🧠 使用贪心前，问自己三句话：
我的贪心策略是什么？
有没有反例能推翻它？
能不能用反证法/交换法证明它正确？

✋ 动手试试

试试 1：实现活动选择问题。输入 n=5，活动为 (1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11), (8,12), (2,13), (12,14)。用贪心选出的最多活动数是多少？手工画出时间轴验证。

试试 2：在找零钱问题中，改变硬币面值为 {1, 3, 4}，测试金额 6。对比贪心结果和手动找到的最优解。修改面值为 {1, 5, 11}，测试金额 15。贪心对吗？

试试 3：实现排队接水，用 n=5, t={3, 1, 4, 2, 5}。手工计算如果按原序和排序后的总等待时间，对比结果。

⚠️ 容易犯的错

错 1：不看问题性质直接贪心

❌ 遇到最优化问题就贪心 → 可能答案是错的

✅ 先找反例，能推翻就说明贪心不适用

错 2：排序的 key 选错了

❌ 活动选择按开始时间排序 → 可能选出一个很长的活动堵住后面的

✅ 活动选择按结束时间排序

错 3：贪心策略正确但实现有 bug

❌ if (a[i].s > lastEnd) 写成了 >=，漏掉了刚好接上的活动

✅ 看清题意：开始时间等于上一个结束时间算不算冲突

错 4：没考虑数据范围

❌ 排队接水用 int 存总等待时间，n=100000 时溢出

✅ 大规模数据用 long long

📝 练习

基础题

1. 选择题

（1）贪心算法的核心特征是？
A. 每步选局部最优 B. 回溯所有可能 C. 用数组记忆 D. 二分搜索

（2）活动选择问题中，贪心按什么排序？
A. 开始时间 B. 时长 C. 结束时间 D. 重要性

（3）以下哪个问题贪心一定能得到最优解？
A. 0-1 背包 B. 硬币找零（任意面值） C. 最优装载 D. 旅行商问题

2. 填空题

（1）贪心算法____回头、____之前的选择。

（2）贪心需要两个性质：____选择性质和____子结构。

（3）排队接水按____排序，总等待时间最小。

提高题

3. 编程题 — 合并果子（贪心思想）

有 n 堆果子，每堆有 aᵢ 个。每次合并任意两堆，代价为两堆果子数之和。问合并成一堆的最小总代价。

提示：每次选最小的两堆合并（需要优先队列/堆，但这里只要求你理解贪心策略）。

4. 编程题 — 区间覆盖

数轴上有 n 个闭区间 [lᵢ, rᵢ]。选择最少的区间，使得它们完全覆盖 [0, L]。

贪心策略：在覆盖了 [0, pos] 的前提下，每次选左端点 ≤ pos 且右端点最大的区间。

挑战题

5. 编程题 — 国王游戏（贪心+高精度）

n 个大臣，每人左手和右手各有一个数 aᵢ 和 bᵢ。国王也在最前面。每个大臣获得的奖赏 = 前面所有人左手数之积 / 自己右手的数。求奖赏最多的大臣最少能获得多少。

提示：按 aᵢ × bᵢ 从小到大排序（需要证明！）。数据可能很大，需要高精度。

🧠 本章小结

贪心 = 每步选局部最优

框架：
  while (还有选择) { 选当前最优; 更新候选集; }

经典问题：
  找零钱    → 先选大面值（面值有要求！）
  最优装载  → 先装轻的
  活动选择  → 按结束时间排序
  排队接水  → 快的排前面

证明方法：
  反证法：假设贪心不是最优，推导矛盾
  交换法：最优解中交换两个元素不会变差
  归纳法：前 k 步贪心正确 → 第 k+1 步也正确

⚠ 陷阱：局部最优 ≠ 全局最优
  · 0-1 背包用价值密度贪心是错的
  · 找零钱在非标准面值下贪心可能错
  · 用贪心前先找反例！

📝 配套练习

共8题。贪心五种模式：按时间/按结束/性价比/相邻约束/分组配对——每种一题。。★核心（课堂必做） ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1223	https://hydro.ac/p/luogu-P1223	排队接水、按时间贪心
◆ 拓展	luogu-P1803	https://hydro.ac/p/luogu-P1803	活动选择、按结束时间贪心
◆ 拓展	luogu-P1090	https://hydro.ac/p/luogu-P1090	合并果子、priority_queue贪心
◆ 拓展	luogu-P3817	https://hydro.ac/p/luogu-P3817	贪心、相邻约束
◆ 拓展	luogu-P2240	https://hydro.ac/p/luogu-P2240	部分背包、性价比贪心
◆ 拓展	luogu-P1478	https://hydro.ac/p/luogu-P1478	贪心、陶陶摘苹果升级
◆ 拓展	luogu-P1208	https://hydro.ac/p/luogu-P1208	贪心、牛奶采购
◆ 拓展	luogu-P1094	https://hydro.ac/p/luogu-P1094	贪心、纪念品分组

💡 练习建议：先完成 1 道★核心题，确保掌握本章基本方法；再完成 7 道◆拓展题，覆盖不同变式和细节。

配套练习

共8题。贪心五种模式：按时间/按结束/性价比/相邻约束/分组配对——每种一题。★核心（课堂必做） · ◆拓展（课后练习）

级别	题号	链接	覆盖知识点
★ 核心	luogu-P1223	https://hydro.ac/p/luogu-P1223	排队接水、按时间贪心
◆ 拓展	luogu-P1803	https://hydro.ac/p/luogu-P1803	活动选择、按结束时间贪心
◆ 拓展	luogu-P1090	https://hydro.ac/p/luogu-P1090	合并果子、priority_queue贪心
◆ 拓展	luogu-P3817	https://hydro.ac/p/luogu-P3817	贪心、相邻约束
◆ 拓展	luogu-P2240	https://hydro.ac/p/luogu-P2240	部分背包、性价比贪心
◆ 拓展	luogu-P1478	https://hydro.ac/p/luogu-P1478	贪心、陶陶摘苹果升级
◆ 拓展	luogu-P1208	https://hydro.ac/p/luogu-P1208	贪心、牛奶采购
◆ 拓展	luogu-P1094	https://hydro.ac/p/luogu-P1094	贪心、纪念品分组

练习建议：先在课堂完成 1 道★核心题，掌握本章基本方法；课后完成 7 道◆拓展题，覆盖不同变式和细节。

自查清单：

[ ] 我理解贪心"每步选最优、永不回头"的特点
[ ] 我能区分贪心和 DP 的适用场景
[ ] 我能实现活动选择、排队接水、最优装载
[ ] 我知道硬币找零的贪心在什么条件下有效
[ ] 我能用反证法/交换法简单证明贪心正确性
[ ] 我能举出贪心失效的反例

🚀 下章预告：贪心是"一条路走到黑"，而分治恰恰相反——它把大问题切成好几个小问题，各自解决后再拼起来。归并排序你已经学过了，但分治的视野远不止排序——最大子段和、最近点对……第 49 章，我们来一场"化整为零"的战术演练！🧩

第 48 章 贪心算法——局部最优的智慧 ​

🎯 本章目标 ​

📖 故事引入 ​

🧱 知识讲解 ​

48.1 贪心思想：每步选最好的 ​

48.2 贪心 vs DP ​

48.3 经典贪心一：找零钱 ​

48.4 经典贪心二：最优装载 ​

48.5 经典贪心三：活动选择（区间调度） ​

48.6 经典贪心四：排队接水 ​

48.7 贪心的陷阱：局部最优 ≠ 全局最优 ​

✋ 动手试试 ​

⚠️ 容易犯的错 ​

错 1：不看问题性质直接贪心 ​

错 2：排序的 key 选错了 ​

错 3：贪心策略正确但实现有 bug ​

错 4：没考虑数据范围 ​

📝 练习 ​

基础题 ​

提高题 ​

挑战题 ​

🧠 本章小结 ​

📝 配套练习 ​

配套练习 ​