算法笔记:AcWing - 贪心算法
💡 写在前面:贪心不是一种算法,而是一种思维方式。它的核心就一句话:每一步都做出当前看起来最优的选择。但难点在于——你怎么证明这个”局部最优”能推出”全局最优”?这篇笔记会带你理解贪心的本质。
什么是贪心?
核心思想:每一步都选择当前状态下看起来最优的决策,期望通过一系列局部最优达到全局最优。
形象理解:想象你在爬山,贪心就是”每次都往最陡的方向走”。但问题是——你可能爬到的是个小山丘,而不是真正的最高峰。
关键特点:
- ✅ 没有固定模板:贪心是思路,不是套路
- ✅ 短视行为:只看眼前,不管长远
- ✅ 难点在证明:为什么这样贪心是对的?
什么时候能用贪心?
只有当问题具有贪心选择性质和最优子结构时,贪心才能得到最优解。简单说就是:
- 局部最优能推出全局最优
- 问题的最优解包含子问题的最优解
⚠️ 重要提醒:如果问题不是”单峰”的(有多个局部最优),贪心很可能掉进陷阱!
区间问题
区间问题是贪心的经典应用场景。核心思路:先排序,再扫描。
🎯 区间选点
问题描述:给定 N 个闭区间 [ai, bi],在数轴上选择尽量少的点,使得每个区间内至少包含一个点。输出最少点数。
贪心策略:
- 将所有区间按右端点从小到大排序
- 依次枚举每个区间:
- 如果当前区间未被覆盖 → 选择它的右端点
- 如果已被覆盖 → 跳过
代码实现:
1 | int main() { |
🤔 灵魂三问
Q1:为什么要按右端点排序,而不是左端点?
答:想象你在”消灭”区间。右端点越小的区间,它的”生存空间”越靠左,能覆盖它的点的选择范围越窄。这种区间最”挑剔”,必须优先满足!
1 | 区间 A: [1, 2] ← 右端点小,只能选 1 或 2 |
如果先处理 B,选了 10,那 A 就没人管了。但如果先处理 A,选了 2,B 也被覆盖了。先满足挑剔的,宽松的后面自然能沾光。
Q2:为什么选右端点,不选左端点或中间?
答:选右端点是为了让这个点尽可能覆盖后面的区间。
1 | 区间 A: [1, 5] |
- 如果选 A 的左端点
1:只能覆盖 A - 如果选 A 的右端点
5:能覆盖 A 和 B!
右端点是当前区间能贡献的”最远覆盖点”,当然选它!
Q3:怎么证明这个贪心是对的?
答:用反证法 + 构造法。
设我们的贪心策略选了 cnt 个点,对应 cnt 个互不相交的区间(因为每个新区间都没被前一个点覆盖)。
关键观察:这 cnt 个区间两两不相交,所以至少需要 cnt 个点(每个区间至少一个点,且不能共用)。
既然任何方案都至少需要 cnt 个点,而我们的贪心正好用了 cnt 个点,那贪心就是最优的!∎
🔗 最大不相交区间数量
问题描述:给定 N 个区间,选出尽量多的区间,使得它们两两不相交。求最多能选多少个。
答案:和区间选点做法完全一致!
为什么? 这两题是对偶问题:
- 区间选点:最少用多少个点,覆盖所有区间
- 最大不相交区间:最多选多少个区间,使得它们不共用任何点
根据上面的证明,贪心选出的 cnt 个区间是互不相交的,且任何方案都不可能超过 cnt 个。所以答案就是 cnt。
💡 数学之美:这两个问题本质是同一个问题的两面,就像”最少需要多少个哨兵看守所有城堡”和”最多能建多少个互不瞭望的城堡”。
📦 区间分组
问题描述:给定 N 个区间,将它们分成若干组,使得每组内部的区间两两不相交,求最小组数。
贪心策略:
- 按左端点从小到大排序
- 依次处理每个区间,判断能否放入某个现有组
- 如果能放 → 放入并更新该组的右端点;否则 → 开新组
核心问题:如何快速判断”能否放入某个组”?
一个区间能放入某组的条件:它的左端点 > 该组所有区间的最大右端点。
所以需要维护:所有组的最大右端点,并快速找到 < 当前左端点 的那个。
解法一:multiset
1 | int main() { |
解法二:小根堆(更优)
1 | int main() { |
为什么堆更优?
multiset:O(n log n),但常数较大priority_queue:O(n log n),常数小,代码更简洁
💡 理解技巧:把每个组想象成一个”教室”,右端点是这个教室当前课程的结束时间。新课程来了,看有没有教室已经空出来了(结束时间 < 新课程开始时间),有就用,没有就开新教室。
🛤️ 区间覆盖
问题描述:给定 N 个区间和一个目标区间 [st, ed],选出最少的区间,使得它们的并集能覆盖 [st, ed]。
贪心策略:
- 按左端点从小到大排序
- 从
st开始,在所有能覆盖当前起点的区间中,选右端点最大的 - 更新起点为这个最大右端点,重复直到覆盖
ed
直观理解:想象你在铺路,每次都要选能接上当前路面、且能铺得最远的那块砖。
1 | int main() { |
时间复杂度:O(n log n)(排序)+ O(n)(扫描)= O(n log n)
Huffman 树
问题描述:给定 n 个权值,构造一棵二叉树,使得带权路径长度最小。每次合并两个节点,合并代价是两节点权值之和。
贪心策略:每次合并权值最小的两个节点。
为什么对?
- 权值最小的两个节点,深度一定最深(否则可以交换使答案更优)
- 它们可以互为兄弟(不影响最优性)
实现:用小根堆维护
1 | int main() { |
应用场景:
- 数据压缩(Huffman 编码)
- 最优合并策略
时间复杂度:O(n log n)
排序不等式
排序不等式:设有两组数 a₁ ≤ a₂ ≤ ... ≤ aₙ 和 b₁ ≤ b₂ ≤ ... ≤ bₙ,则:
简单说:同序和 ≥ 乱序和 ≥ 逆序和
💧 打水问题
问题描述:n 个人排队打水,第 i 个人需要 t[i] 时间。求总等待时间最小的排队顺序。
贪心策略:按打水时间从小到大排序。
直观理解:让打水快的人先打,后面的人等待时间就短。如果让慢的人先打,所有人都要等他很久。
数学推导:
设排序后的时间为 t₁ ≤ t₂ ≤ ... ≤ tₙ,则:
- 第 1 个人等待
0 - 第 2 个人等待
t₁ - 第 3 个人等待
t₁ + t₂ - …
- 第
i个人等待t₁ + t₂ + ... + tᵢ₋₁
总等待时间:
系数 (n-i) 是递减的,根据排序不等式,t 应该递增排列。
1 | int main() { |
绝对值不等式
🏪 货仓选址
问题描述:在数轴上有 n 个商店,位置分别为 x₁, x₂, ..., xₙ。要建一个货仓,使得所有商店到货仓的距离之和最小。求货仓的最佳位置。
贪心策略:货仓建在中位数位置。
为什么? 用配对法理解:
把商店按位置排序后,考虑最左和最右的商店 x₁ 和 xₙ:
- 无论货仓建在哪,
|x - x₁| + |x - xₙ|的最小值就是xₙ - x₁(当x在两者之间时取到)
同理,x₂ 和 xₙ₋₁ 配对,x₃ 和 xₙ₋₂ 配对…
结论:
n为奇数:货仓建在正中间的商店x[n/2]n为偶数:货仓建在中间两个商店之间的任意位置(通常取x[n/2])
1 | int main() { |
💡 形象理解:想象你在拉橡皮筋,左边商店把你往左拉,右边商店把你往右拉。平衡点就是中位数!
推公式型贪心
很多贪心问题需要先模拟、找规律、推公式。核心方法:分析交换两个元素的影响。
🐂 耍杂技的牛
问题描述:n 头牛叠罗汉,第 i 头牛有体重 w[i] 和力量 s[i]。每头牛的危险系数 = 它上面所有牛的体重之和 - 它的力量。求最大危险系数的最小值。
贪心策略:按 w[i] + s[i] 从小到大排序。
🤔 为什么是 w + s?(详细证明)
考虑相邻的两头牛 i 和 i+1,分析交换它们的影响。
关键观察:交换相邻两头牛,不影响其他牛的危险系数,只影响这两头牛。
设前 i-1 头牛的体重和为 W,则:
交换前(i 在上,i+1 在下):
- 牛
i的危险系数:W - s[i] - 牛
i+1的危险系数:W + w[i] - s[i+1] - 最大危险系数:
max(W - s[i], W + w[i] - s[i+1])
交换后(i+1 在上,i 在下):
- 牛
i+1的危险系数:W - s[i+1] - 牛
i的危险系数:W + w[i+1] - s[i] - 最大危险系数:
max(W - s[i+1], W + w[i+1] - s[i])
去掉公共项 W,比较:
- 交换前:
max(-s[i], w[i] - s[i+1]) - 交换后:
max(-s[i+1], w[i+1] - s[i])
两边同时加上 s[i] + s[i+1](不改变大小关系):
- 交换前:
max(s[i+1], w[i] + s[i]) - 交换后:
max(s[i], w[i+1] + s[i+1])
结论:如果 w[i] + s[i] < w[i+1] + s[i+1],则交换前的最大值更小,不应该交换。
所以最优排列是:按 w + s 递增排序!∎
代码实现:
1 | int main() { |
💡 理解技巧:w + s 可以理解为”综合负担能力”。w + s 小的牛,要么体重轻(压别人少),要么力量小(容易被压),应该放上面。
📝 贪心总结
| 问题类型 | 贪心策略 | 排序方式 | 核心思想 |
|---|---|---|---|
| 区间选点 | 选右端点 | 右端点升序 | 先满足挑剔的 |
| 最大不相交区间 | 同上 | 右端点升序 | 对偶问题 |
| 区间分组 | 放入最早结束的组 | 左端点升序 | 小根堆维护 |
| 区间覆盖 | 选能接上且最远的 | 左端点升序 | 每次铺最远 |
| Huffman 树 | 合并最小的两个 | 小根堆 | 深度最深 |
| 打水问题 | 快的先打 | 时间升序 | 排序不等式 |
| 货仓选址 | 建在中位数 | 位置升序 | 配对法 |
| 耍杂技的牛 | 按 w+s 排序 | w+s 升序 | 交换分析法 |
🎯 贪心解题套路
- 猜贪心:根据直觉猜一个贪心策略
- 验证:
- 举反例:能不能找到反例?
- 交换分析:交换两个元素会变好吗?
- 数学归纳:能证明吗?
- 实现:通常是”排序 + 扫描”
🍂 最后的话:贪心的难,不在于代码,而在于证明。多做题、多思考”为什么这样是对的”,你会逐渐培养对贪心的直觉。记住:能证明的贪心才是好贪心!
- Title: 算法笔记:AcWing - 贪心算法
- Author: Ginkgo
- Created at : 2026-04-12 16:12:02
- Updated at : 2026-04-12 16:21:49
- Link: https://g1nkgo7.github.io/2026/04/12/算法笔记-AcWing-贪心/
- License: This work is licensed under CC BY-NC-SA 4.0.