前面十八章里，你写的每一个算法都能「讲清楚为什么对」： 递归是分解，二分靠单调，DFS/BFS 是把所有情况都走了一遍。
贪心不一样。贪心的代码通常短得离谱 —— 这一章的两道题，正解都只有一行 sort 加一个循环。 但它是唯一一类**「写出来只要三分钟，证明它对要一小时」**的算法。
所以这一章的重点从头到尾只有一件事：怎么确认你的贪心不是在瞎猜。 方法有两个，都要学会： 交换论证（用脑子证）和对拍（用机器验）。缺一个都不够 —— 证明能给你信心，对拍能救你的命。
1 一句话问题（一）：排队接水
n 个人排队接水，只有一个水龙头，第 i 个人接水要 t[i] 分钟。
排在第 k 位的人，要干等前面 k-1 个人接完。
求一种排队顺序，使所有人等待时间之和最小。
输入 4
7 3 5 1
输出 142 先用手算一遍
拿 7 3 5 1 试两种顺序：
| 顺序 | 各自等待 | 总等待 |
|---|---|---|
7 3 5 1（原顺序） | 0, 7, 10, 15 | 32 |
1 3 5 7（从小到大） | 0, 1, 4, 9 | 14 |
差了一倍多。为什么差这么多？看这个式子：
总等待 = 0·t[排第1] + 1·t[排第2] + 2·t[排第3] + 3·t[排第4]排在越前面的人，他的接水时间被越多人「重复承担」：第一个人的时间要被后面 3 个人一起等， 最后一个人的时间谁也不用等。
所以直觉很清楚了：让被乘上大系数的那个数尽量小 —— 快的先接。
但「直觉很清楚」不等于「它是对的」。下面先写一份绝对不会错的暴力，把这个直觉钉死。
3 暴力：n! 种顺序全试一遍
点「运行 ▶」看结果
用 next_permutation 枚举全部 n! 种排队顺序，每种算一遍总等待，取最小。
它慢得离谱，但它不需要任何聪明的想法 —— 这正是它作为标准答案的价值。
4 实测：暴力慢在哪
本机实测：
| n | 全排列暴力 | 排序贪心 |
|---|---|---|
| 10 | 0.034 秒 | 0.005 秒 |
| 11 | 0.36 秒 | 0.005 秒 |
| 12 | 4.3 秒 | 0.005 秒 |
| 13 | 62.9 秒 | 0.005 秒 |
| 200000 | 等到宇宙凉了 | 0.023 秒 |
n 每加 1，暴力就慢 n 倍（0.034 → 0.36 是 10 倍，0.36 → 4.3 是 12 倍，4.3 → 62.9 是 14.6 倍）。
这就是 n! 的样子 —— 比第 3 章那个 2ⁿ 还要凶得多。
贪心那一栏的 0.005 秒其实是量不出来：本机空跑一个什么都不做的 C++ 程序 （启动进程、读几个数、退出）也要 4~5 毫秒。真正花在算法上的时间比这还小。 只有把 n 拉到 20 万，才勉强量出 0.023 秒。
5 ★ 关键一步：交换论证
要证明「按 t 从小到大排是最优的」，不需要考虑全部 n! 种顺序，只需要盯住相邻的两个人。
设某个排法里，相邻的两位接水时间是 a 和 b，a 排在前，且 a > b（慢的排在快的前面）。
把这两个人交换一下，总等待时间会怎么变？
他们站在第 k、k+1 位。第 k 位的人，他的接水时间要被后面 n-k 个人等；
第 k+1 位的被 n-k-1 个人等。别的人完全不受影响（他们前面那堆人的总时间没变）。于是：
交换前 = (n-k)·a + (n-k-1)·b
交换后 = (n-k)·b + (n-k-1)·a
差 = (b - a)·[(n-k) - (n-k-1)] = b - a总等待时间正好减少 a - b 分钟 —— 而且和他们站在第几位完全无关。
于是：只要队伍里还存在「慢的排在快的前面」的相邻一对，这个排法就一定不是最优的 （因为交换一下就更好了）。反过来说，最优解里不可能有这样的一对。 没有任何一对相邻逆序 = 整个队伍是升序。
这就是交换论证（exchange argument），贪心正确性证明里最常用的一招。它的套路永远是三句话：
- 假设最优解和贪心解不一样；
- 找到第一个不一样的地方，把它换成贪心的选择；
- 说明换完之后答案不会变差 —— 于是贪心解也是最优的。
6 把交换论证跑一遍给你看
光看推导容易「看过就忘」。下面这份代码从你给的任意顺序出发， 每次找最左边那对「慢的在前」交换掉，并打印总等待时间少了多少：
点「运行 ▶」看结果
7 3 5 1 要交换 5 次才排好，总等待从 32 一路降到 14。
这个「反复交换相邻逆序对」的过程，就是第 10 章的冒泡排序。
而交换的次数 —— 5 次 —— 正好是 7 3 5 1 的逆序对个数（第 11 章）。
不是巧合：交换一对相邻的逆序，逆序对总数不多不少刚好减少 1。
所以「把任意顺序改进到最优」需要的交换次数，就是逆序对个数。
swap.cpp 最后一行会把这两个数并排打出来给你核对。
7 正解
点「运行 ▶」看结果
把 fast.cpp 和 brute.cpp 并排看：算总等待的那个循环一个字都没改。
唯一的区别是 brute.cpp 算了 n! 种顺序，而 fast.cpp 只算了一种 —— 升序那种。
复杂度 O(n log n)，全花在排序上。
n = 10⁵、t 最大 10³ 时，总等待时间可以到 10⁵ × 10⁵ × 10³ / 2 = 5 × 10¹² 量级 ——
int 装不下。
而对拍永远不会告诉你这件事：对拍用的是 n ≤ 8 的小数据，
小数据下 int 和 long long 的行为完全一样。这只能靠脑子。
规矩很简单：只要答案是「一堆数加起来 / 乘起来」，一律先写 long long。
8 动画：看着总等待时间一次次掉下去
浅色那一段是「干等」，深色那一段才是「在接水」。要最小化的就是所有浅色段的总长度。
建议这样玩：
- 点「改成最坏顺序（降序）」，看初始的总等待有多大；
- 一步一步点，盯住「这一步少了」那一栏 —— 它永远等于被交换的两个数之差；
- 播到底，确认「总等待时间」和右边「全排列暴力的答案」对上了。
9 一句话问题（二）：区间调度
换一道题，同样是排序型贪心，但该按什么排没那么显然了。
n 场比赛，第 i 场占用时间段 [l, r]。你同一时刻只能参加一场，
但上一场结束的时刻可以正好是下一场开始的时刻（[1,3] 和 [3,5] 不冲突）。
最多能参加几场？
「端点重合算不算冲突」是题目规定的，不是数学定理。 本章按洛谷 P1803 的约定：端点重合不算冲突。
这句话决定了代码里写 l >= lastEnd 还是 l > lastEnd —— 一个字之差，答案就不一样。
对拍的两份程序如果对这句话的理解不同，你会调一整晚，还以为是算法错了。
10 三种「听起来都对」的排法
拿到这题，几乎所有人都会想到按某个东西排序。候选有三个：
- 按开始时间从早到晚 —— 早点开始，能多参加几场？
- 按持续时间从短到长 —— 挑短的，占的时间少？
- 按结束时间从早到晚 —— 早点结束，留给后面的时间多？
三个听起来都很有道理。而只有第三个是对的。 下面这份代码把三种排法并排跑给你看 （第四行是 2ⁿ 暴力，当尺子）：
点「运行 ▶」看结果
本机跑出来：
| 策略 | 选出的场数 |
|---|---|
| ① 按左端点从早到晚 | 3 |
| ② 按区间从短到长 | 3 |
| ③ 按右端点从早到晚 | 4 |
| ④ 2ⁿ 暴力（一定最优） | 4 |
它们分别错在哪：
- ① 按开始时间：
[1,10]开始得最早，可它一个人就占掉了整个上午 —— 本来能参加[2,3]和[4,5]两场的。开始得早，不代表结束得早。 - ② 按持续时间：
[14,16]只有 2 个单位，看起来很划算， 可它正好卡在[12,15]和[15,18]中间 —— 一个换掉了俩。
11 ★ 关键一步：为什么是「结束最早」
直觉版：结束得越早，留给后面的时间就越多。 这是唯一一个直接对「后面还剩多少空间」负责的指标。
严格版（还是交换论证）：
设贪心选的第一场是 Y（全场结束最早的那一场），而某个最优解按时间排好后第一场是 X。
因为 Y 是结束最早的，所以 Y.r <= X.r。
现在把最优解里的 X 换成 Y：
原来能排在 X 后面的那些场次，开始时间都 >= X.r >= Y.r，
所以它们照样能排在 Y 后面。于是：
- 场数一个都没少（换掉一场，补上一场）；
- 而且现在这个最优解的第一场和贪心一致了。
对剩下的部分重复同样的论证，就能把最优解一步步「掰」成贪心解，而场数从头到尾没变过。 所以贪心解和最优解一样多。∎
注意这个论证的形状和排队接水一模一样： 「假设最优解和我不同 → 把它改成和我一样 → 证明改完不会更差」。
12 正解 + 实测
点「运行 ▶」看结果
标准答案是 2ⁿ 枚举子集（接第 3 章的二进制枚举）：
本机实测：
| n | 2ⁿ 暴力 | 排序贪心 |
|---|---|---|
| 22 | 0.052 秒 | 0.005 秒 |
| 24 | 0.218 秒 | 0.005 秒 |
| 26 | 0.67 秒 | 0.005 秒 |
| 28 | 3.5 秒 | 0.005 秒 |
| 200000 | 想都别想 | 0.039 秒 |
13 动画：同一组比赛，三种排法
只改左上角那个下拉框，别的什么都不动，看三种排法分别选出几场。
要盯的是：错误的那两种是在哪一步走岔的 —— 它们不是一开始就错， 而是在某一步贪了一个「看起来划算」的区间，然后为此赔上了后面两场。
14 ★ 对拍：贪心最需要对拍
前面几章的对拍，抓的多半是写错（边界、越界、剪过头）。
贪心不一样：贪心的对拍抓的是想错。 你的代码可能一个字都没写错，编译零警告，样例全过 —— 但排序的关键字选错了， 于是它在 90% 的数据上都对，只在某一类数据上崩。
这种错误只有对拍能发现。 而且你会发现：造出反例往往只需要三五轮随机数据。 下面两个对拍器，把「正解」那一栏换成你自己写的（尤其推荐故意换成「按左端点排」）， 点开始，看着自己的直觉在第几轮被打脸。
排队接水（标准答案 = 全排列暴力）：
区间调度（标准答案 = 2ⁿ 枚举子集）：
值得故意写错、然后看对拍怎么抓的：
- 排序写成从大到小 → 第 1 轮就被抓
total += wait和wait += t[i]两行调换 → 把自己的接水时间也算成了等待，第 1 轮被抓- 区间按左端点排 → 通常 2~3 轮内被抓
l >= lastEnd写成l > lastEnd（把端点重合当成冲突）→ 第 1 轮被抓， 因为生成器专门造了大量端点重合的数据- 总和用
int→ 对拍抓不住（小数据不会溢出），只能靠第 7 步那个规矩
15 排序型贪心的通用套路
-
猜一个排序关键字。 排序型贪心的答案几乎总是「按某个东西排序，然后顺着扫一遍」。 先把候选列出来：开始时间、结束时间、长度、大小、比值……
-
试着做交换论证。 假设最优解和你的贪心在某处不同，把那一处换成贪心的选择， 看答案会不会变差。
- 论证得通 → 你的贪心是对的，而且你知道它为什么对；
- 论证卡住了 → 八成是排序关键字选错了，换一个再试。
-
不管论证通没通，都去对拍。 论证可能出错，代码可能和论证不一致。 标准答案用完全不同的思路写（全排列 / 2ⁿ 枚举 / DP），别用同一个想法写两遍。
-
实在证不出来，就别用贪心。 说不出交换论证，只能靠「感觉」， 那就老老实实上搜索或 DP（阶段 5）—— 慢一点的正确算法，永远好过快一点的错误算法。
第 16 章那道小猫爬山也是「一只一只安排」，为什么那里贪心不行，这里就行？
区别在于当前的选择会不会影响后面的可能性：
- 排队接水：把谁排在前面，不改变后面还能怎么排 —— 只影响系数。贪心可行。
- 区间调度：选了结束最早的那场，后面能选的只会变多不会变少（交换论证证明的就是这件事）。贪心可行。
- 装箱（小猫爬山）：这只猫塞进哪辆车，会实实在在地改变后面每辆车的剩余容量， 一步走错满盘皆输。贪心不可行，只能搜索。
判断不了的时候，就用第 3 步：对拍。 三分钟就能知道答案。
16 自测
- 洛谷 P1223 排队接水 —— 本章原题。注意它要输出的是排队顺序和平均等待时间（保留两位小数），比本章多一步输出格式
- 洛谷 P1803 凌乱的yyy / 线段覆盖 —— 本章第二道题的原题，端点重合的约定也和这里一致
- 洛谷 P2240 部分背包问题 —— 按「单位价值」排序 —— 排序关键字是算出来的，不是直接给的。想清楚交换论证为什么在这里成立（而在 01 背包里不成立，见第 23 章）
- 洛谷 P1094 纪念品分组 —— NOIP2007。排序之后用第 7 章的对撞双指针，最贵的配最便宜的。交换论证要动点脑筋
- 洛谷 P1090 合并果子 —— NOIP2004。每次合并最小的两堆 —— 但一次排序不够用，因为合并出来的新堆还要重新参与排序。这题在等第 37 章的堆，先用 sort 硬做也能过
第 20 章把这一章的第 3 步单独拎出来讲透：用对拍系统地打假错误的贪心。
那一章的主角不是正确的算法，而是四个「看起来非常对」的贪心， 每一个都配一个能在几轮内打假它的对拍器 —— 包括那个几乎人人都会上当的 「背包按性价比排序」。
学完这一章你会写贪心了，学完下一章你才敢在考场上写贪心。