“The greedy algorithm is a good algorithm to talk about because it is easy to understand, and it is easy to implement, but it is a perfect example of a case where you have to prove that it is correct.” – Thomas H. Cormen
本笔记为 第六讲 · 贪心算法 的 C++ 模板与题解，内容涵盖区间贪心、排序策略、Huffman树、以及多种基于不等式和邻项交换证明的经典贪心模型。
贪心算法，一种在算法世界中追求“眼前最优”的智慧。它不着眼于全局的复杂算计，而是专注于在每个决策点上做出当下看来最好的选择。这种简洁而强大的思想，常常能为复杂问题提供出人意料的高效解法。本章将带你深入探索贪心策略的奥秘，从经典的区间问题到精巧的排序模型，学习如何识别贪心性质，并用代码将这种“局部最优”的智慧转化为通往“全局最优”的捷径。[胭脂水色]
💰 第六讲 贪心算法
🧠 1. 贪心算法基础
🎯 1.1 核心思想
贪心算法（Greedy Algorithm）在求解问题时，并不从整体最优上加以考虑，而是做出在当前看来是最好的选择。也就是说，不追求长远，只顾“眼前利益”。其核心是：
- 局部最优：在问题的每个阶段，都选择当前状态下的最优解。
- 全局最优：期望通过一系列的局部最优选择，最终能够得到问题的全局最优解。
这种算法思想简单、直观且高效，但其正确性需要严格的证明。
✅ 1.2 适用条件
并非所有问题都能用贪心算法解决。一个问题能使用贪心算法求解，通常需要满足以下两个性质：
- 贪心选择性质（Greedy Choice Property）： 通过局部最优的选择，不会破坏全局最优解的构建，即局部最优解可以构成全局最优解的一部分。
- 最优子结构（Optimal Substructure）： 问题的最优解可以通过其子问题的最优解来构造，即问题可以被分解为互不相干的子问题，并且其最优解包含子问题的最优解。
🪜 1.3 设计步骤
设计一个贪心算法通常遵循以下步骤：
- 问题建模： 明确问题的输入、输出以及需要达到的最优目标。
- 证明贪心选择性质： 分析问题，证明每次局部选择不会影响全局最优性。如果没有这一步，贪心算法可能只得到一个次优解。
- 建立排序或优先级结构： 贪心算法常常需要先将数据按照某种关键指标排序（例如活动选择问题中按结束时间排序），或者使用优先队列来动态选择最佳候选。
- 设计循环结构： 遍历数据，根据贪心策略判断是否选择某个元素，并更新状态。
- 返回结果： 将构造的解返回，同时分析时间复杂度与空间复杂度。
下面是一些经典贪心模型与实例。
📏 2. 区间问题
区间问题是贪心算法的经典应用场景，通常需要对区间的某个端点进行排序。
📍 2.1 区间选点
🗂️ 2.1.1 洛谷 & 牛客题单
| 来源 | 题目/题单 | 说明 |
|---|---|---|
| 洛谷 | https://www.luogu.com.cn/problem/U248666 | U248666 区间选点 |
| 洛谷 | https://www.luogu.com.cn/problem/U380776 | U380776 区间选点 |
| 洛谷 | https://www.luogu.com.cn/problem/T464757 | T464757 区间选点问题 |
| 洛谷 | https://www.luogu.com.cn/problem/T355666 | T355666 【5-2练习B】区间选点问题 |
| 洛谷 | https://www.luogu.com.cn/problem/T505759 | T505759 区间选点 |
| 洛谷 | https://www.luogu.com.cn/problem/U207087 | U207087 练习-区间选点问题 |
| 洛谷 | https://www.luogu.com.cn/problem/U336172 | U336172 区间选点 |
| 洛谷 | https://www.luogu.com.cn/problem/U212594 | U212594 区间选点 |
| 洛谷 | https://www.luogu.com.cn/problem/U183399 | U183399 [YBT] 整数区间|区间选点 |
❓💡2.1.2 问题和解法
问题描述
给定 N 个闭区间
[a_i, b_i]，请你在数轴上选择尽量少的点，使得每个区间内至少包含一个选出的点。输出选择的点的最小数量。
（1）贪心策略
1、将所有区间按照 右端点 b_i 从小到大排序。
2、遍历排序后的区间：
选择第一个区间的右端点作为第一个点。
对于后续区间，如果它的左端点 a_i 大于上一个选定点的坐标，说明当前区间未被覆盖，此时需要选择当前区间的右端点作为新的点。
（2）证明：选择右端点作为新的选点，是因为它最有可能覆盖到后续更多的区间，从而使得总选点数最少。
（3）代码实现
写法1：按右端点升序
// 闭区间，按右端点从小到大排序
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator<(const Range& t) const {
return r < t.r; // 按右端点从小到大排序
}
} range[N];
int n;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
int ans = 0, lastR = -2e9; // lastR 记录上一次已经选中的最右端点
for (int i = 0; i < n; ++i) {
if (lastR < range[i].l) {
++ans;
lastR = range[i].r;
}
}
printf("%d\n", ans);
return 0;
}
写法2：按左端点降序（对称操作）
// 按左端点从大到小排序
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator<(const Range& t) const {
return l > t.l; // 按左端点从大到小排序
}
} range[N];
int n;
int main() {
scanf("%d", &n);
for (int i = 0; i < n; ++i) scanf("%d%d", &range[i].l, &range[i].r);
sort(range, range + n);
// lastL记录上次已经选中的最左端点
int ans = 0, lastL = 2e9;
for (int i = 0; i < n; ++i) {
if (lastL > range[i].r) {
++ans;
lastL = range[i].l;
}
}
printf("%d\n", ans);
return 0;
}
📈 2.2 最大不相交区间数量
🗂️ 2.2.1 洛谷 & 牛客题单
| 来源 | 题目/题单 | 说明 |
|---|---|---|
| 洛谷 | https://www.luogu.com.cn/problem/U248675 | U248675 最大不相交区间数量 |
| 洛谷 | https://www.luogu.com.cn/problem/T642681 | T642681 【模板】区间最大不相交问题 |
| 洛谷 | https://www.luogu.com.cn/problem/U238066 | U238066 最大不相交区间数量 |
| 洛谷 | https://www.luogu.com.cn/problem/U380775 | U380775 区间最大不相交问题 |
| 洛谷 | https://www.luogu.com.cn/problem/U212595 | U212595 最大不相交区间数量 |
| 洛谷 | https://www.luogu.com.cn/problem/T505760 | T505760 最大不相交区间数量 |
| 洛谷 | https://www.luogu.com.cn/problem/U336178 | U336178 最大不相交区间数量 |
| 洛谷 | https://www.luogu.com.cn/problem/P1803 | P1803 凌乱的yyy / 线段覆盖 |
❓💡2.2.2 问题和解法
问题描述
给定 N 个闭区间
[a_i, b_i]，请你在数轴上选择若干区间，使得选中的区间之间互不相交（包括端点）。输出可选取区间的最大数量。
（1）贪心策略 此问题的贪心策略与 区间选点 完全一致。
将所有区间按照 右端点 b_i 从小到大排序。
选择第一个区间，然后遍历后续区间，如果当前区间的左端点 a_i 大于已选区间的最后一个的右端点，则选择当前区间。
（2）证明：每次选择右端点最小的区间，可以为后续留下尽可能多的“空闲”空间，从而容纳更多的区间。
（3）代码实现
（代码与“区间选点”问题完全相同）
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator<(const Range& t) const {
return r < t.r; // 按右端点从小到大排序
}
} range[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d", &range[i].l, &range[i].r);
}
sort(range, range + n);
int ans = 0;
int lastR = -2e9; // 记录上一个选中区间的右端点
for (int i = 0; i < n; ++i) {
if (range[i].l > lastR) {
ans++;
lastR = range[i].r;
}
}
printf("%d\n", ans);
return 0;
}
📦 2.3 区间分组
🗂️ 2.3.1 洛谷 & 牛客题单
| 来源 | 题目/题单 | 说明 |
|---|---|---|
| 洛谷 | https://www.luogu.com.cn/problem/U248679 | U248679 区间分组 |
| 洛谷 | https://www.luogu.com.cn/problem/T533921 | T533921 区间分组 |
| 洛谷 | https://www.luogu.com.cn/problem/U492913 | U492913 区间分组 |
| 洛谷 | https://www.luogu.com.cn/problem/U380779 | U380779 区间分组 |
| 洛谷 | https://www.luogu.com.cn/problem/T664751 | T664751 区间分组 |
| 洛谷 | https://www.luogu.com.cn/problem/U336186 | U336186 区间分组 |
| 洛谷 | https://www.luogu.com.cn/problem/U212597 | U212597 区间分组 |
| 洛谷 | https://www.luogu.com.cn/problem/P2434 | P2434 [SDOI2005] 区间 |
❓💡2.3.2 问题和解法
问题描述
给定 N 个闭区间
[a_i, b_i]，请你将这些区间分成若干组，使得每组内部的区间两两之间没有交集，并使得组数尽可能小。输出最小组数。
（1）贪心策略
1、将所有区间按照 左端点 a_i 从小到大排序。
2、维护一个存储各组当前最右端点的小根堆。
3、遍历排序后的区间：
如果当前区间的左端点 a_i 大于 堆顶元素（即某一组的最右端点），说明可以将该区间放入该组。更新该组的最右端点（弹出堆顶，压入当前区间的右端点 b_i）。
否则，当前区间无法放入任何现有组，必须开一个新组。将该区间的右端点 b_i 压入堆中。
4、最终堆的大小即为最小组数。
（2）代码实现
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator<(const Range& t) const { return l < t.l; }
} range[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) { scanf("%d%d", &range[i].l, &range[i].r); }
sort(range, range + n);
priority_queue<int, vector<int>, greater<int>>pq; // 小根堆，存储每组最右端点
for (int i = 0; i < n; ++i) {
if (pq.empty() || range[i].l <= pq.top()) {
// 开新组
pq.push(range[i].r);
} else {
// 放入现有组
pq.pop();
pq.push(range[i].r);
}
}
printf("%d\n", pq.size());
return 0;
}
🧩 2.4 区间覆盖
🗂️ 2.4.1 洛谷 & 牛客题单
| 来源 | 题目/题单 | 说明 |
|---|---|---|
| 洛谷 | https://www.luogu.com.cn/problem/U248682 | U248682 区间覆盖 |
| 洛谷 | https://www.luogu.com.cn/problem/U380778 | U380778 区间覆盖 |
| 洛谷 | https://www.luogu.com.cn/problem/U492914 | U492914 区间覆盖 |
| 洛谷 | https://www.luogu.com.cn/problem/T664753 | T664753 区间覆盖 |
| 洛谷 | https://www.luogu.com.cn/problem/U310416 | U310416 区间覆盖 |
| 洛谷 | https://www.luogu.com.cn/problem/U207088 | U207088 区间覆盖问题 |
| 洛谷 | https://www.luogu.com.cn/problem/U236112 | U236112 【贪心】区间线段覆盖问题 |
| 洛谷 | https://www.luogu.com.cn/problem/P2082 | P2082 区间覆盖（加强版） |
| 洛谷 | https://www.luogu.com.cn/problem/U430784 | U430784 区间覆盖究极加强版 |
❓💡2.4.2 问题和解法
问题描述
给定 N 个闭区间
[a_i, b_i]以及一个线段区间[s, t]，请你选择尽量少的区间，将指定线段区间完全覆盖。输出最少区间数，如果无法完全覆盖则输出 -1。
（1）贪心策略
1、将所有区间按照 左端点 a_i 从小到大排序。
2、设当前已覆盖区间的右端点为 start（初始为 s）。
3、在所有左端点 a_i <= start 的区间中，选择一个 右端点最大 的区间 [a_j, b_j]。
4、将 start 更新为 b_j，计数器加一。
5、重复步骤 3 和 4，直到 start >= t。如果在某一步中找不到满足条件的区间，则无解。
（2）代码实现
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1e5 + 10;
struct Range {
int l, r;
bool operator<(const Range& t) const { return l < t.l; }
} range[N];
int main() {
int s, t, n;
scanf("%d%d", &s, &t);
scanf("%d", &n);
for (int i = 0; i < n; ++i) { scanf("%d%d", &range[i].l, &range[i].r); }
sort(range, range + n);
int ans = 0;
bool success = false;
for (int i = 0; i < n; ++i) {
int j = i, max_r = -2e9;
// 在所有能覆盖当前 s 点的区间里，找右端点最远的
while (j < n && range[j].l <= s) {
max_r = max(max_r, range[j].r);
j++;
}
if (max_r < s) { // 找不到能覆盖 s 的区间
ans = -1;
break;
}
ans++;
if (max_r >= t) { // 成功覆盖
success = true;
break;
}
s = max_r; // 更新起点
i = j - 1; // 更新i到检查过的位置
}
if (!success) ans = -1;
printf("%d\n", ans);
return 0;
}
🌳 3. Huffman 树模型
Huffman 树是贪心思想的完美体现，常用于解决“合并代价”最小化问题。
🍎 3.1 合并果子
🗂️ 3.1.1 洛谷 & 牛客题单
| 来源 | 题目/题单 | 说明 |
|---|---|---|
| 洛谷 | https://www.nowcoder.com/practice/854e7118eb08464ab8ce7a0bca8b276c | 合并果子 |
| 洛谷 | https://www.nowcoder.com/practice/162753046d5f47c7aac01a5b2fcda155 | 哈夫曼树 |
| 洛谷 | https://www.luogu.com.cn/problem/P1090 | P1090 [NOIP 2004 提高组] 合并果子 |
| 洛谷 | https://www.luogu.com.cn/problem/T685337 | T685337 合并果子 |
| 洛谷 | https://www.luogu.com.cn/problem/U530232 | U530232 [Luke_xiao round 1] 合并果子 |
| 洛谷 | https://www.luogu.com.cn/problem/T574557 | T574557 [NOIP 2004 提高组] 合并果子 |
| 洛谷 | https://www.luogu.com.cn/problem/T508078 | T508078 【5-2练习C】合并果子 |
| 洛谷 | https://www.luogu.com.cn/problem/P6033 | P6033 [NOIP 2004 提高组] 合并果子 加强版（普及+/提高） |
| 洛谷 | https://www.luogu.com.cn/training/498220 | 哈夫曼树（题单） |
| 洛谷 | https://www.luogu.com.cn/training/243380 | 【Tea徐】入门组训练（哈夫曼树）（题单） |
| 洛谷 | https://www.luogu.com.cn/training/507114 | 二叉树和哈夫曼树（题单） |
| 洛谷 | https://www.luogu.com.cn/training/468140 | 哈夫曼树(S组)（题单） |
❓💡3.1.2 问题和解法
问题描述 (P1090 [NOIP 2004 提高组] 合并果子)
有 n 堆果子，每堆的果子数量已知。每次可以合并任意两堆果子，消耗的体力等于两堆果子的数量之和。经过 n-1 次合并后，所有果子会变成一堆。求耗费的体力总和的最小值。
（1）贪心策略 要使总代价最小，每次应选择当前数量最少的两堆果子进行合并。因为数量少的果子在合并树的底层，它们被计算的次数（深度）最多，将小数放在底层能使总和最小。这正是 Huffman 树 的构造过程。
1、使用小根堆维护所有果子堆。
2、循环 n-1 次：
从堆中取出最小的两个数 x 和 y。
将它们的和 x+y 累加到总代价中。
将新堆 x+y 重新放入小根堆。
3、最终累加的代价即为最小体力耗费。
（2）代码实现
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n;
int main() {
scanf("%d", &n);
priority_queue<int, vector<int>, greater<int>> q;
while (n--) {
int x;
scanf("%d", &x);
q.push(x);
}
int ans = 0;
while (q.size() > 1) {
int x = q.top();
q.pop();
int y = q.top();
q.pop();
ans += x + y;
q.push(x + y);
}
printf("%d\n", ans);
return 0;
}
⚖️ 4. 排序不等式模型
排序不等式指出，顺序和 ≥ 乱序和 ≥ 逆序和。利用此性质可以解决一些与求和最小/最大相关的问题。
💧 4.1 排队打水
🗂️ 4.1.1 洛谷 & 牛客题单
| 来源 | 题目/题单 | 说明 |
|---|---|---|
| 洛谷 | https://www.luogu.com.cn/problem/P1223 | P1223 排队接水 |
| 洛谷 | https://www.luogu.com.cn/problem/U235350 | U235350 排队接水 |
| 洛谷 | https://www.luogu.com.cn/problem/U283548 | U283548 【贪心】接水问题 |
❓💡4.1.2 问题和解法
问题描述 (P1223 排队接水)
有 n 个人排队接水，每个人接水的时间为
T_i。请安排一个顺序，使得所有人的 总等待时间 最小。
（1）贪心策略
总等待时间 = 0 + T_1 + (T_1+T_2) + ... + (T_1+...+T_{n-1})
整理后可得 = (n-1)T_1 + (n-2)T_2 + ... + 1*T_{n-1}
根据排序不等式，要使这个和最小，应该让较小的 T_i 乘以较大的系数 (n-i)。因此，贪心策略是：让接水时间短的人排在前面。
1、将每个人的接水时间 T_i 从小到大排序。
2、按排序后的顺序计算总等待时间。
（2）代码实现
#include <algorithm>
#include <iostream>
using namespace std;
const int N = 1005;
struct Person {
int id;
int time;
bool operator<(const Person& other) const {
return time < other.time;
}
} p[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
p[i].id = i;
scanf("%d", &p[i].time);
}
sort(p + 1, p + 1 + n);
long long total_wait_time = 0;
long long current_time = 0;
for (int i = 1; i < n; ++i) {
printf("%d ", p[i].id);
current_time += p[i].time;
total_wait_time += current_time;
}
printf("%d\n", p[n].id);
printf("%.2f\n", (double)total_wait_time / n);
return 0;
}
注：原题要求输出平均等待时间，但最小化总等待时间等价于最小化平均等待时间。
🏠 5. 绝对值不等式模型
形如 $\sum{|x - a_i|}$ 的式子，其几何意义是数轴上一点 x 到若干点 a_i 的距离之和。
🏭 5.1 货仓选址
🗂️ 5.1.1 洛谷 & 牛客题单
| 来源 | 题目/题单 | 说明 |
|---|---|---|
| 牛客 | https://www.nowcoder.com/practice/4938eb9320214ff48583e87bcf4db15e | 仓库选址 |
| 洛谷 | https://www.luogu.com.cn/problem/P10452 | P10452 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/T507182 | T507182 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/U208125 | U208125 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/U216784 | U216784 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/T445072 | T445072 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/U270934 | U270934 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/U167449 | U167449 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/T663533 | T663533 作业题：货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/U212641 | U212641 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/T551808 | T551808 货仓选址(12-15) |
| 洛谷 | https://www.luogu.com.cn/problem/T516247 | T516247 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/U186336 | U186336 选址 |
| 洛谷 | https://www.luogu.com.cn/problem/T508088 | T508088 【5-1例题C】货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/U587418 | U587418 0x05 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/U520107 | U520107 货仓选址 |
| 洛谷 | https://www.luogu.com.cn/problem/T446368 | T446368 货仓选址 |
❓💡5.1.2 问题和解法
问题描述
在一条数轴上有 N 家商店，坐标分别为
A_1, ..., A_N。需要在数轴上建立一家货仓，使得货仓到每家商店的距离之和最小。求这个最小距离和。
（1）贪心策略
问题是找到一个点 x，最小化 Σ|x - A_i|。根据绝对值不等式的结论，当 x 选在所有坐标 A_i 的 中位数 时，该距离和最小。
1、将所有商店的坐标 A_i 排序。
2、选择中位数 A[n/2] 作为货仓位置。
3、计算所有商店到该中位数的距离之和。
（2）代码实现
#include <algorithm>
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d", &a[i]);
}
sort(a, a + n);
int median_pos = a[n / 2];
long long sum_dist = 0;
for (int i = 0; i < n; ++i) {
sum_dist += abs(a[i] - median_pos);
}
printf("%lld\n", sum_dist);
return 0;
}
🤝 6. 推公式（邻项交换证明模型）
对于一些排序贪心问题，其排序依据不直观，常通过“邻项交换法”（或称“微扰法”）来证明其正确性。
🐄 6.1 耍杂技的牛
🗂️ 6.1.1 洛谷 & 牛客题单
| 来源 | 题目/题单 | 说明 |
|---|---|---|
| 洛谷 | https://www.luogu.com.cn/problem/P1842 | P1842 [USACO05NOV] 奶牛玩杂技 |
| 洛谷 | https://www.luogu.com.cn/problem/T508090 | T508090 【5-2例题A】奶牛玩杂技 |
❓💡6.1.2 问题和解法
问题描述 (P1842 [USACO05NOV] 奶牛玩杂技)
N 头牛叠罗汉，每头牛有体重
W_i和力量S_i。一头牛的压扁指数定义为它上方所有牛的总重减去它的力量。所有牛叠完后，找出所有牛中压扁指数的最大值。要求设计一种顺序，使得这个最大值最小。
（1）贪心策略
考虑任意相邻的两头牛 i 和 j，假设 i 在 j 上方。
j 的压扁指数为 ... + W_i - S_j，i 的压扁指数为 ... - S_i。
如果交换它们，j 在 i 上方：
i 的压扁指数为 ... + W_j - S_i，j 的压扁指数为 ... - S_j
比较交换前后的压扁指数最大值，可以发现，为了使最大值更小，应该满足 W_i + S_i < W_j + S_j 的牛排在上方。因此，贪心策略是：将所有牛按照 W_i + S_i 的和从小到大排序。
（2）代码实现
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int N = 50010;
struct Cow {
int w, s;
};
bool compareCows(const Cow& a, const Cow& b) {
return a.w + a.s < b.w + b.s;
}
Cow cows[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; ++i) {
scanf("%d%d", &cows[i].w, &cows[i].s);
}
sort(cows, cows + n, compareCows);
long long sum_w = 0;
long long max_risk = -2e9; // 压扁指数可能为负
for (int i = 0; i < n; ++i) {
// 对于第i头牛，它头上的重量是 sum_w
long long risk = sum_w - cows[i].s;
max_risk = max(max_risk, risk);
sum_w += cows[i].w;
}
printf("%lld\n", max_risk);
return 0;
}