前言
前面五章用了各种技巧——暴力、搜索、数学、数据结构、图论、DP。这一章回到最直觉的策略：每一步都选眼前最好的选择。这就是贪心（Greedy）。
贪心之所以难，不在于”怎么贪”，而在于”凭什么贪是对的”。DP 通过枚举所有状态保证最优，但贪心只走一条路——如果这条路不对，就全盘皆输。所以证明贪心的正确性才是核心技能。
最常用的证明方法是交换论证：假设最优解在某一步和贪心不同，证明把它们交换过来不会更差。如果每一步都能这样交换，那贪心解就一定是最优的。
问题的本质
贪心什么时候有效？
贪心有效的前提是贪心选择性质：存在一个最优解，它的第一步和贪心的选择一样。如果这个性质成立，我们就可以放心地做贪心第一步，然后对剩余子问题继续贪心。
常见的贪心有效场景：
- 排序后配对：两组数一一配对，最小化距离和（排序后对应配对）
- 按截止时间/结束时间排序：区间调度（选结束最早的）
- 按报酬排序：每个时间点选最大可用报酬（Taro’s Job）
- 中位数选址：曼哈顿距离之和最小化
交换论证：为什么排序配对是最优的？
以 T90 014 为例： 个学生和 个学校分别在不同位置，一一配对使总距离最小。
贪心策略：两组都排序，第 小的学生配第 小的学校。
证明：假设最优解中，第 小的学生 配了第 小的学校 （），而第 小的学校 配了某个更大的学生 （）。交换这两对： 配 ， 配 。因为 且 ，可以证明交换后总距离不会增加（三角不等式）。重复交换，最终得到排序配对——说明排序配对不比最优解差。
理论 + 代码
模型一：排序配对
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int N;
scanf("%d", &N);
int A[100009], B[100009];
for (int i = 0; i < N; i++) scanf("%d", &A[i]);
for (int i = 0; i < N; i++) scanf("%d", &B[i]);
sort(A, A + N); // ① 学生位置排序
sort(B, B + N); // ② 学校位置排序
long long ans = 0;
for (int i = 0; i < N; i++)
ans += abs(A[i] - B[i]); // ③ 对应配对
printf("%lld\n", ans);
}逐行解析：
- ①② 两组都升序排序。
- ③ 第 小配第 小。为什么这是最优的？交换论证——任何交叉配对都可以”理顺”而不增加总距离。
模型二：中位数选址（曼哈顿距离）
坐标和 坐标独立。 在 = 中位数时最小。这是因为：中位数左侧有 个点，右侧也有 个点。把 左移 1，右侧 个点的距离各减 1，左侧 个点各加 1，净效果可能更差。所以中位数是最优点。
例题
例题 1：T90 014 — We Used to Sing a Song Together（★3，排序配对）
题目： 个学生在位置 ， 个学校在位置 。每个学生去不同学校，最小化总距离 。
数据范围：
分析：排序配对贪心。两组排序后一一配对。
输入样例：
6
8 6 9 1 2 0
1 5 7 2 3 9输出：5
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int N;
scanf("%d", &N);
int A[100009], B[100009];
for (int i = 0; i < N; i++) scanf("%d", &A[i]);
for (int i = 0; i < N; i++) scanf("%d", &B[i]);
sort(A, A + N); // ① 排序
sort(B, B + N);
long long ans = 0;
for (int i = 0; i < N; i++)
ans += abs(A[i] - B[i]); // ② 对应配对
printf("%lld\n", ans);
}逐行解析：
- ① 两组都升序排序。。
- ②
abs(A[i] - B[i])就是第 小学生到第 小学校的距离。
验证：，。配对：。✓
例题 2：T90 070 — Plant Planning（★4，中位数选址）
题目： 个工厂坐标 。选一个发电所位置使曼哈顿距离总和最小。
数据范围：
分析：x 和 y 独立。 在 取中位数时最小。排序后取中间值。
输入样例：
2
-1 2
1 1输出：3
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int N;
scanf("%d", &N);
long long X[100009], Y[100009];
for (int i = 0; i < N; i++) scanf("%lld%lld", &X[i], &Y[i]);
sort(X, X + N); // ① x 坐标排序
sort(Y, Y + N); // ② y 坐标排序
long long mx = X[N / 2]; // ③ x 中位数
long long my = Y[N / 2]; // ④ y 中位数
long long ans = 0;
for (int i = 0; i < N; i++)
ans += abs(X[i] - mx) + abs(Y[i] - my); // ⑤ 曼哈顿距离总和
printf("%lld\n", ans);
}逐行解析：
- ①② 和 坐标分别排序。
- ③④ 取中位数。 为偶数时取
X[N/2]即可（任何两个中间值之间的点都一样优）。 - ⑤ 对每个工厂计算曼哈顿距离并累加。
验证：，。X 排序 ，中位数 或 （取 ）。Y 排序 ，中位数 。选 ：。✓
例题 3：TB B39 — Taro’s Job（贪心选工作）
题目： 天、 个工作。工作 在第 天后可选，报酬 。每天最多做 1 个工作。求最大总报酬。
数据范围：，
分析：教材 6.4 节。贪心策略：从第 1 天到第 天，每天选所有已解锁工作中报酬最大的。用优先队列维护。
为什么从第 1 天开始而不是从第 天倒推？因为工作一旦解锁就一直可用。从前往后遍历，每天把 的工作加入候选，选最大的做。
代码：
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
int main() {
int N, D;
scanf("%d%d", &N, &D);
pair<int, int> jobs[200009]; // (X_i, Y_i)
for (int i = 0; i < N; i++) scanf("%d%d", &jobs[i].first, &jobs[i].second);
sort(jobs, jobs + N); // ① 按 X_i 排序
priority_queue<int> pq; // ② 最大堆
long long ans = 0;
int idx = 0;
for (int day = 1; day <= D; day++) {
while (idx < N && jobs[idx].first <= day) {
pq.push(jobs[idx].second); // ③ 新解锁的工作加入堆
idx++;
}
if (!pq.empty()) {
ans += pq.top(); // ④ 选报酬最大的
pq.pop();
}
}
printf("%lld\n", ans);
}逐行解析：
- ① 按 （解锁日期）排序，这样每天只需把新的工作加入堆。
- ② 最大堆（
priority_queue默认最大堆），存放已解锁但未做的工作的报酬。 - ③ 所有 的工作在此刻解锁，加入堆。
- ④ 每天选堆顶（最大报酬）的工作做。
验证：，工作 。
| 天 | 新解锁 | 堆内容 | 选择 | 累计 |
|---|---|---|---|---|
| 1 | (1,1) | {1} | 1 | 1 |
| 2 | (2,4),(2,3) | {4,3} | 4 | 5 |
| 3 | (3,4) | {4,3} | 4 | 9 |
| 4 | (4,2) | {3,2} | 3 | 12 |
答案 = 12。✓
例题 4：TB A38 — Black Company 1（贪心上界）
题目： 天劳动计划，每天 0-24 小时。 个条件： 期间最勤劳日不超过 小时。求最大总劳动时间。
数据范围：，
分析：每天最多 24 小时，但受到多个条件限制。对每一天 ，它被所有满足 的条件覆盖。为了满足所有条件，第 天的工作时间不能超过 。没有条件覆盖的天可以工作 24 小时。
贪心策略：对每天取所有覆盖条件的 最小值，没有条件的取 24。
代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int D, N;
scanf("%d%d", &D, &N);
int limit[366];
for (int i = 1; i <= D; i++) limit[i] = 24; // ① 初始每天最多 24 小时
for (int i = 0; i < N; i++) {
int L, R, H;
scanf("%d%d%d", &L, &R, &H);
for (int d = L; d <= R; d++)
limit[d] = min(limit[d], H); // ② 取最小上界
}
int ans = 0;
for (int i = 1; i <= D; i++)
ans += limit[i]; // ③ 累加每天的最大工时
printf("%d\n", ans);
}逐行解析：
- ① 初始假设每天都可以工作 24 小时。
- ② 每个条件限制 期间所有天都不超过 。对涉及的天取 min。
- ③ 每天取到了所有条件的交集（最小上界），全部加起来就是最大总工时。
验证：，条件 。
| 天 | 条件覆盖 | limit |
|---|---|---|
| 1 | 22 | |
| 2 | min(22,16)=16 | |
| 3 | min(16,23)=16 | |
| 4 | 23 | |
| 5 | 23 |
答案 = 22+16+16+23+23 = 100。✓
例题 5：TB A40 — Triangle（计数正三角形）
题目： 根棒，长度 。选 3 根不同的棒组成正三角形，有多少种选法？
数据范围：，
分析：正三角形需要三条边等长。所以选 3 根长度相同的棒。统计每个长度出现次数 ，答案 = 。
代码：
#include <cstdio>
using namespace std;
int cnt[109]; // cnt[x] = 长度 x 出现次数
int main() {
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
int a; scanf("%d", &a);
cnt[a]++; // ① 统计频次
}
long long ans = 0;
for (int x = 1; x <= 100; x++) {
long long c = cnt[x];
if (c >= 3)
ans += c * (c - 1) * (c - 2) / 6; // ② C(c, 3)
}
printf("%lld\n", ans);
}逐行解析：
- ① 用桶计数统计每个长度出现的次数。 所以只需 101 个桶。
- ② 。从 根等长棒中选 3 根的组合数。
验证：。长度 1 出现 4 次，。长度 2 出现 3 次，。答案 = 5。✓
参考文献
教材讲解 — 競技プログラミングの鉄則 第 6 章
系统练习 — 競技プログラミングの鉄則
- A38 Black Company 1（贪心上界）【例题】
- A40 Triangle（计数正三角形）【例题】
- B36 Switching Lights（开关灯贪心）
- B37 Sum of Digits（数位和）
- B38 Heights of Grass（贪心+排序）
- B39 Taro’s Job（贪心选工作+优先队列）【例题】
- B40 Divide by 100（贪心模拟）
- B41 Reverse of Euclid（贪心构造）
- B42 Two Faced Cards（贪心+分类）
- B43 Quiz Contest（贪心+计数）
- B44 Grid Operations（贪心+行列表操作）
- B45 Blackboard 2（贪心+符号判定）
实战练习 — 競プロ典型 90 問
- 014 We Used to Sing a Song Together（★3，排序配对）【例题】
- 070 Plant Planning（★4，中位数选址）【例题】
- 079 Two by Two（★3，贪心操作）
基础练习 — アルゴリズムと数学 演習問題集
系列索引
第零章 基础工具
第一章 搜索技术
第二章 数学基础
第三章 数据结构
- 03-01 栈、队列与单调栈
- 03-02 堆与优先队列
- 03-03 并查集
- 03-04 树状数组
- 03-05 线段树
- 03-06 懒标记线段树
- 03-07 Sparse Table 与倍增
- 03-08 字符串哈希
第四章 图论
- 04-01 图的遍历
- 04-02 最短路—Dijkstra 与 01-BFS
- 04-03 最短路—Bellman-Ford 与 Floyd
- 04-04 拓扑排序
- 04-05 最小生成树
- 04-06 强连通分量与 2-SAT
- 04-07 二分图与网络流
- 04-08 树上问题
第五章 动态规划
- 05-01 DP入门—状态与转移
- 05-02 背包问题族
- 05-03 LIS、LCS与编辑距离
- 05-04 区间DP
- 05-05 状态压缩DP
- 05-06 树形DP与数位DP
- 05-07 矩阵快速幂与线性递推
第六章 贪心
第七章 字符串
第八章 进阶