贪心算法 知识点讲解

概念

想象你在超市买东西，规定「每样只能拿一件，要装进一个承重 10 斤的袋子，怎么拿最值钱」。你当然想拿最贵的 —— 但最贵的可能一下就 9 斤，装完只剩 1 斤空间浪费了。

贪心就是：每一步都做「当下看起来最划算」的那个选择，并且赌它最后就是全局最优。

关键在于后半句：几乎所有同学都会「做最划算的选择」，但能不能说明它为什么一定最优，才是贪心题的分水岭。

很多同学的痛点是：看得出这题要用贪心，但不敢肯定自己对不对，于是写成 DP 或者干脆骗分。其实贪心有固定的验证套路（找反例 + 交换论证），学过之后就能自己判断。

触发清单（看到这些信号第一时间想到本知识点）

定义

贪心成立的判断标准（也就是"为什么可以对"）：

1. 贪心选择性质：每一步的局部最优选择，一定属于某个全局最优解；

2. 最优子结构：做完这一步选择后，剩下的问题是同一类问题的更小规模。

一个反例就能否掉贪心——这是最实用的方法。看 0/1 背包：

袋子承重 10。物品：A(重 9，价值 10)、B(重 6，价值 7)、C(重 5，价值 6)。 「先拿最贵的」→ 拿 A，剩 1 斤装不下别的，总价值 10。 而拿 B + C（重 11？不行）…… 换一组：A(重 9，价 10)、B(重 5，价 6)、C(重 5，价 6)。 拿 A → 总价值 10；拿 B + C → 总价值 12。贪心输了。 所以 0/1 背包不能贪心，必须 DP。

常用贪心策略对照表（先认题型，再套策略）：

️ 知识用法地图（先记这张表，后面每节都会回到它）

贪心最怕「局部最优 ≠ 全局最优」。下面推三个让你「敢贪」的依据。

推演 1 · 为什么「排序后顺序取」常是最优（交换论证）

若最优解里某两个相邻元素的相对顺序与「按关键字排序」不同，交换它们不会让结果更差（交换论证）。因此「按关键字排序后贪心取」一定包含了最优解。这是排序贪心的正确性根基。

用法：能排序后贪心的题，先证「交换相邻不更差」，再放心取。

推演 2 · 反悔贪心为什么正确

先做直观选择，同时用堆记录「已选集合里最该被替换的那个」。发现更优解时，把堆顶换掉——等价于在「局部最优可能错」时留了后悔药。最终等价于整体最优，但避免了枚举所有选择。

用法：出现「选了之后可能要换更划算的」（合并果子、廊桥），用堆维护反悔。

推演 3 · 拼数为什么按 a+b < b+a 排序

比较「ab」与「ba」谁字典序小，保证拼出来最小。这本质是交换论证在字符串拼接上的直接应用：若 a+b < b+a，则任何含 a,b 相邻的最优排列里 a 必在 b 前。

用法：拼接类题（拼数、构造最大数）用 a+b 与 b+a 比较，别比数值大小。

原讲义配图

例题

例题 1：排队接水

题目描述

有 $n$ 个人在排队接水，第 $i$ 个人接水需要 $t_i$ 分钟。每个人都要等待前面所有人接完水才能开始。求所有人等待时间之和的最小值。

审题分析

• 读题抓条件：等待时间 = 前面所有人接水时间之和。
• 定需求：最小化总等待时间。
• 为什么能用本知识点：总等待时间 = $\sum_{i=1}^n t_i \times (n-i)$。要让总和最小，系数大的 $t_i$ 必须乘小的 $(n-i)$，即接水时间短的人必须排在前面。
• 如果不用本知识点：若按任意顺序，总等待时间固定为上述公式，无法优化。

解题思路

按接水时间从小到大排序，让接水快的人先接，这样后面的人等待时间就短了。

C++ 完整参考代码

#include <iostream>
#include <algorithm>
using namespace std;

int t[1005];
long long sum; // 总等待时间可能很大，用 long long

int main() {
 int n; cin >> n;
 for (int i = 0; i < n; i++) cin >> t[i];
 sort(t, t + n); // 关键：按接水时间升序排
 for (int i = 0; i < n; i++)
 sum += 1LL * t[i] * (n - 1 - i); // 第 i 人要被后面 (n-1-i) 人等
 cout << sum << endl; // 输出最小总等待时间
 return 0;
}

代码解读

• 输入 $n$ 和数组 $t$。
• sort(t, t + n) 将接水时间从小到大排列。
• 排序后，第 $i$ 个人（0-based）前面有 $i$ 个人，后面有 $n-1-i$ 个人。
• 每个人 $t_i$ 会被后面 $n-1-i$ 个人各等待一次，所以贡献 $t_i \times (n-1-i)$。
• 累加所有贡献得到最小总等待时间。

运行结果

输入：

3
1 3 2

输出：

10

（解释：排序后为 1, 2, 3。总等待 = $1\times2 + 2\times1 + 3\times0 = 2+2+0 = 4$？不对，重新计算：排序后 t[0]=1, t[1]=2, t[2]=3。sum = 1*(3-1-0) + 2*(3-1-1) + 3*(3-1-2) = 1*2 + 2*1 + 3*0 = 2+2+0 = 4。代码实际输出应为 4。修正：上述代码逻辑正确，手动计算有误。正确输出为 4。）

修正运行结果

输入：

3
1 3 2

输出：

4

例题 2：纪念品分组

题目描述

每组最多 2 件纪念品，每组的价值和不能超过 $w$，求最少分成几组。

审题分析

• 读题抓条件：每组最多 2 件，价值和不超过 $w$。
• 定需求：最少组数。
• 为什么能用本知识点：要让组数最少，就要尽可能每组 2 件。让最贵的和能配上的最便宜的一件配对（配不上就自己一组），这样既没超限，又省下了一件，后面的分组只会更轻松。
• 如果不用本知识点：若随意配对，可能浪费空间，导致组数增多。

解题思路

把纪念品按价格排序，每次让最贵的和能配上的最便宜的一件配对（配不上就自己一组）。

C++ 完整参考代码

#include <iostream>
#include <algorithm>
using namespace std;

int a[1005];
int n, w;
int main() {
 cin >> n >> w;
 for (int i = 0; i < n; i++) cin >> a[i];
 sort(a, a + n); // 按价格升序
 int l = 0, r = n - 1, groups = 0;
 while (l <= r) {
 if (a[l] + a[r] <= w && l < r) { l++; } // 最贵的能带上最便宜的就带上
 r--; groups++; // 否则最贵的自己一组
 }
 cout << groups << endl;
 return 0;
}

代码解读

• 输入 $n, w$ 和数组 $a$。
• 排序后，双指针 $l$ 指向最便宜，$r$ 指向最贵。
• 若 $a[l] + a[r] \le w$ 且 $l < r$，说明最贵的能和最便宜的配对，$l$ 右移。
• 无论是否配对，$r$ 都要右移（最贵的已经处理），组数加 1。
• 循环直到 $l > r$。

运行结果

输入：

5 9
1 2 3 5 8

输出：

3

（解释：排序后 [1, 2, 3, 5, 8]，w=9。8+1=9≤9→{1,8}；5+2=7≤9→{2,5}；3 单独→{3}。共 3 组。）

例题复盘总结

共性特征：排序后扫描 / 双指针配对 / 堆维护极值。

各自技巧：

• 排队接水：按接水时间升序，总等待 = $\sum t_i(n-1-i)$。
• 纪念品分组：双指针首尾配对，配得上就配，配不上最贵的单独一组。
• 合并果子：反悔贪心，堆里放当前最小两堆之和。

审题模板（固定思考流程）：

1. 问「最少 / 最多 / 是否可行」→ 先怀疑贪心。

2. 写出那句策略：「每次都选当前 ___ 最大的 / 最小的」。

3. 手动找反例：拿 3~4 个数据穷举一遍，看贪心会不会输。

4. 确定排序关键字：按值？按比值？按结束时间？

5. 想想「要不要撤销刚才的选择」→ 要的话用堆（反悔贪心）。

错误清单（特有）：

• 双指针配对时忘了 l < r 判断，同一个元素被自己配了两次。
• 堆的默认是大根堆，取最小值必须写 greater<int>，否则静默错误。
• 排序关键字选错：同样是「排序后贪心」，按 值 排和按 值/重量 排结果完全不同。

写法总表

分工：触发清单告诉你「什么时候想到它」，速查表告诉你「想做的事对应什么写法」。

常见错误

1. 凭感觉贪心，不找反例。 贪心最常见的失败不是「写不出来」，而是「写出来是错的」。动手前先拿 3~4 个数据穷举一遍，成本几分钟，能省掉一整题的分。

2. 排序关键字选错。 同样是「排序后贪心」，按 值 排和按 值/重量 排结果完全不同。选关键字前先问：「我这一步要比较的到底是什么？」

3. 该用 DP 却贪心。 看到「选或不选 + 有容量限制」就警觉：这是 0/1 背包，贪心会错。

4. 区间题按左端点排序。 区间调度（最多能选几个不重叠区间）要按右端点升序排；按左端点排是错的典型。

5. 贪心过程要「撤销」时硬写贪心。 如果发现「刚才不该选那个」，说明需要反悔贪心（堆）或 DP，不是继续在贪心上打补丁。

6. 忘记排序本身的开销。 贪心经常靠排序实现，复杂度是 O(n log n) —— 数据到 1e6 时要留意常数。

自测

1. 用一句话说清「贪心选择性质」是什么，以及为什么 0/1 背包不满足它。

2. 区间调度问题（最多能选多少个互不重叠的区间）应该按左端点还是右端点排序？为什么？

3. 「合并果子」为什么可以用堆解决？堆里放的是什么？

举一反三 · 审题流水线

拿到题先问：「我要按什么排序？」—— 排序关键字就是这题贪心策略的全部。答不出关键字的题，先别写。排序之后通常只需要一次线性扫描，如果扫描过程中还要「回头改」，说明这题需要的是反悔贪心或 DP。写完后拿 3~5 个数手推一遍，看是否和穷举结果一致。

练手题

题 1：有 $n$ 个任务，第 $i$ 个任务耗时 $t_i$，完成后获得收益 $v_i$。每次只能做一个任务，做完才能做下一个。求最大总收益。

题 2：有 $n$ 个物品，第 $i$ 个物品重量 $w_i$，价值 $v_i$。背包容量 $W$。每次只能拿一个物品，拿了就占容量。求最大总价值。