接水问题贪心算法：单多水龙头排序与优先队列实现

“接水问题”这个标题在题库里一搜能搜出好几道，输入格式不一样，模型不一样，最优解也不一样，但它们的标签上都写着“贪心算法”。我刚开始刷贪心专题的时候，就是被这种同名不同题的命名坑过一次——看到“接水”两个字，脑子里立刻蹦出“时间短的排前面”，三段排序代码写完交上去，评测机回了一排红。后来把题面逐字读了一遍才发现，那道题里水龙头有 m 个，人的顺序是给定的，根本轮不到我排序。

这篇文章就把“接水问题”这一类题摊开讲透。一类是单水龙头的排队顺序优化，核心是把等待时间总和写成一个求和式，再用相邻交换法把“小的排前面”这件事证明出来；另一类是多水龙头的时间线推进，核心数据结构是优先队列，靠每次把下一个人挂到最早空出的龙头上来完成模拟。前者考的是排序加贪心结论的推导，后者考的是模拟加堆的运用，两者都归在贪心算法这个大类里，但解题动作完全没有重合。

文章会给出完整的推导链条、可以直接复制的 C++ 与 Python 实现、手算验证过程，还会把踩过的坑一条条列出来，包括优先队列默认大根堆这种经典陷阱、平均等待时间的浮点误差、以及“什么时候贪心能用、什么时候必须回头写动态规划”。刚接触贪心的新手可以从头顺着读，有一定基础的读者可以直接跳到推导和实现部分对照自己的写法。

1. 先分清两道题：模型错了，后面全白写

1.1 单水龙头那道题：一个水龙头，n 个人，问怎么排队

这一类的题面通常是这样的：有 n 个人在一个水龙头前排队接水，第 i 个人接满自己那个桶需要 t[i] 的时间。需要你安排这 n 个人的排队顺序，使得所有人的平均等待时间最小，输出这个最小的平均等待时间，有时还要求输出排队的编号顺序。

关键约束是：只有一个水龙头，同一时刻只能有一个人接水，后面的人必须等前面的人接完才能上前。所以第一个人等待时间是 0，第二个人等待的时间是第一个人接水用的时长，第三个人等待的时间是前两个人接水时长之和，依此类推。这个“等待时间”的定义要抠死，因为很多人会下意识地把它和“完成时间”混起来——完成时间是等待时间加上自己的接水时长，两者差的正好是 t[i] 本身，算错了样例就对不上。

这道题的标准答案就是按 t[i] 从小到大排序。但“知道结论”和“能证明结论”是两回事，面试或者比赛复盘的时候，你要是只能说一句“凭直觉应该这样”，那基本等于没说。第 2 节我们会用相邻交换法把这个结论严格推出来。

1.2 m 个水龙头那道题：顺序是给定的，不能重排

另一类题的题面完全不一样：有 m 个水龙头同时开放，n 个人按给定的顺序接水，第 i 个人需要的接水量是 w[i]。开始的时候前 m 个人分别占住 m 个水龙头，之后每当有一个人接完，排在后面的下一个人立刻补上这个空位，直到所有人都接完。问所有人接完水一共需要多少时间。

这道题最关键的一句话是“按给定的顺序”——人的排列是输入给你的，你没有权限去重排。这一条直接把排序这条路堵死了。你唯一能做的决策是：当下一个人需要补位的时候，补到哪个龙头上去。而正确答案也很朴素：补到最早空出来的那个龙头上。这个“最早空出来”，就应该用一个小根堆实时维护。

我第一次做的时候，脑子里的“贪心”就是“排序”，结果写了半天发现题意不允许排序。这两道题经常被放在同一个专题里，标签都写“贪心”，但一个是“排序型贪心”，一个是“模拟型贪心”，性质差了十万八千里。

1.3 两道题的核心差异对照

把这张表记住，比背十道题的代码都有用。看到“接水”两个字，先问自己三个问题：水龙头有几个？人的顺序能不能动？问的是平均等待时间还是总完成时间？这三个问题的答案组合起来，就能立刻定位到对应的解法。

2. 相邻交换法：把“小的排前面”从直觉变成证明

2.1 总等待时间可以改写成一个更友好的求和式

设某个排队顺序为 t[1], t[2], ..., t[n]，下标表示他们接水的先后位置。第 k 个人前面有 k-1 个人，他要等的时间就是这 k-1 个人的接水时长之和。所有人的等待时间总和 W 写成：

W = Σ(k=1..n) Σ(j=1..k-1) t[j]

这个双重求和看着不友好，但换个角度数一下就能化简。我们要数的是每个 t[j] 被加了多少次——t[j] 位于第 j 个位置，它的后面有 n-j 个人，这 n-j 个人每个人等待时都会把 t[j] 算进去一次，所以：

W = Σ(j=1..n) (n-j) · t[j]

这一步是整个证明的地基。它的直观含义是：位置越靠前的人，他的接水时长被越多的人等待。排在第 1 位的那个人，他的 t 被后面 n-1 个人等；排在最后一位的人，他的 t 一次都不会被别人等。所以越大的系数越应该配越小的 t，这就是“小的排前面”的全部秘密。

2.2 交换相邻两个人，看总等待时间怎么变

现在假设有一个排队顺序，其中有相邻的两个人，位置分别是 i 和 i+1，接水时长分别记为 x = t[i] 和 y = t[i+1]。我们只把这两个人换一下位置，其他人的位置完全不动。

先看这两个人在位置 i 和 i+1 上的贡献。根据上面的公式，位置 i 的系数是 n-i，位置 i+1 的系数是 n-i-1。

交换前的贡献： (n-i)·x + (n-i-1)·y 交换后的贡献： (n-i)·y + (n-i-1)·x

做差（交换后减交换前）：

Δ = (n-i)·y + (n-i-1)·x - (n-i)·x - (n-i-1)·y = (n-i)(y - x) + (n-i-1)(x - y) = (y - x) · [(n-i) - (n-i-1)] = y - x

结果干净得让人意外：交换相邻两人的代价，恰好就是这两个人的时长之差，跟他们在哪个位置、队伍有多长都没关系。如果 y < x，也就是后面那个人更快，那么 Δ = y - x < 0，交换之后总等待时间减少。反之如果 y > x，交换会让总等待时间增加，说明原来的顺序在这个局部是对的。

2.3 从局部最优推到全局最优

有了 2.2 的结论，证明剩下两步。

第一步，如果某个顺序不是升序的，那么它一定存在某个位置满足 t[i] > t[i+1]（也就是一个逆序对）。把这两个相邻的人换过来，总等待时间严格变小。第二步，重复做这件事，每换一次逆序对就少一个，队列里的逆序对总数是有限的，最终一定会停在一个没有任何逆序对的排列上——那就是升序排列。

而升序排列已经不可能通过任何相邻交换再变小了（因为任意相邻两个都满足 y ≥ x，Δ ≥ 0）。再补一句：任意排列都可以通过一串相邻交换变到升序，所以升序排列的总等待时间不高于任何其他排列。证毕。

这套方法叫相邻交换论证（exchange argument），是做贪心题最通用的证明工具。它的套路是固定的：先写出目标函数的表达式，再考虑把相邻两个元素对调，算出目标函数的变化量，根据变化量的符号判断谁该在前面。凡是遇到“有一个排列、要让某个总量最优”的贪心题，第一反应就该是这套方法。

2.4 平均等待时间与总等待时间：那个容易翻车的除法

题目要的是平均等待时间，等于总等待时间除以人数 n。这里有两个小地方容易出错。

第一个是精度。总等待时间可能很大，比如 n = 1000、时长最大 1000，那么 W 的数量级大约在 1000 × 1000 × 1000 / 2 = 5×10^8，用 32 位有符号整数就已经贴着上限了。n 再大一点直接溢出。所以累加变量必须用 64 位整数，PHP 之外的绝大多数语言里就是 long long / int64。

第二个是输出格式。如果题目要求保留两位小数，用浮点除法输出就行；但如果要求输出一个分数或者精确到某个小数位，那就得考虑用整数除法加余数手动格式化，避免 double 在极端数据下最后一位抖动。我自己习惯的写法是：先算整数部分和余数部分，再拼字符串，这样完全不会碰到浮点误差。

long long total = 0; // ... 累加过程 long long integer_part = total / n; long long remainder = total % n; // remainder 部分按需要决定要不要四舍五入

还有一个概念上的坑：有些题问的是“所有人接完水的总时间”，也就是最后一个人完成接水的时刻，这个量等于 Σ t[i]，跟排队顺序完全无关。我见过有人把这个问题和总等待时间搞混，然后很困惑“为什么排了序答案没变”。看到这类问法，先判断目标函数里到底有没有“等待”这个动作的累加。

3. 单水龙头题的完整实现与编号输出

3.1 用前缀和一遍扫出总等待时间

有了公式 W = Σ(n-j)·t[j]，代码其实一行循环就能搞定。但更直观、更不容易写错的写法是模拟“逐个人上前接水”的过程，用一个变量 cur 记录当前已经流逝的时间，也就是当前这个人开始接水前要等待的时长：

sort(t.begin(), t.end()); long long total = 0, cur = 0; for (int i = 0; i < n; ++i) { total += cur; // 这个人等待的时间 cur += t[i]; // 他接完之后，时间线推进 } double ans = (double)total / n;

这段代码的逻辑非常好读：cur 从 0 开始，第一个人等 0，接完把 cur 推进到 t[0]；第二个人等 cur = t[0]，接完 cur 变成 t[0] + t[1]，以此类推。它和公式 W = Σ(n-j)·t[j] 是等价的，两种写法都可以，选自己不容易写乱的那种。

我个人的偏好是这种“时间线推进”的写法，因为它在后面多水龙头那道题里也能复用，思路连贯。

3.2 要输出原始编号时怎么处理

如果题目还要求输出排队顺序的编号，那就不能在排序的时候把编号弄丢。两个常用做法。

做法一，排序下标数组：

vector<int> id(n); iota(id.begin(), id.end(), 0); sort(id.begin(), id.end(), [&](int a, int b) { return t[a] < t[b]; }); for (int i = 0; i < n; ++i) printf("%d ", id[i] + 1);

做法二，直接用 pair：

vector<pair<int,int>> a(n); for (int i = 0; i < n; ++i) a[i] = {t[i], i + 1}; sort(a.begin(), a.end()); // 先按时间，时间相同按编号

pair 的默认比较是字典序，时间相同时按编号排。这里有个细节值得说清楚：时间相同的两个人，谁先谁后对总等待时间没有任何影响，因为交换论证里 Δ = y - x = 0，换了也不变。所以当题目要求输出某个“标准答案”顺序时，通常会明确规定“时间相同时按编号从小到大”，你按 pair 排序天然就满足；如果题目没规定，一般会有 special judge 来核对。

3.3 两份可以直接抄的实现

C++ 版本：

#include <bits/stdc++.h> using namespace std; int main() { int n; if (scanf("%d", &n) != 1) return 0; vector<pair<int,int>> a(n); for (int i = 0; i < n; ++i) { scanf("%d", &a[i].first); a[i].second = i + 1; } sort(a.begin(), a.end()); long long total = 0, cur = 0; for (int i = 0; i < n; ++i) { total += cur; cur += a[i].first; printf("%d", a[i].second); if (i + 1 < n) putchar(' '); } putchar('\n'); printf("%.2f\n", (double)total / n); return 0; }

Python 版本：

import sys def main(): data = sys.stdin.read().split() if not data: return n = int(data[0]) t = list(map(int, data[1:1 + n])) order = sorted(range(n), key=lambda i: (t[i], i)) total = 0 cur = 0 for i in order: total += cur cur += t[i] print(" ".join(str(i + 1) for i in order)) print(f"{total / n:.2f}") main()

两个版本都处理了编号输出和两位小数。Python 里 sorted 的 key 用了元组 (t[i], i)，正好把“时间相同时按编号”这条规则写进去了。

提示：.2f在 Python 里用的是银行家舍入（round half to even），而 C 的 printf 通常用的是 round half away from zero。如果题目对某个恰好 .005 的边界值有严格判定，两个语言的输出可能会不一样。真遇到这种数据，老老实实手写四舍五入的整数逻辑。

4. 多水龙头题：小根堆模拟时间线的正确姿势

4.1 为什么“排序后平均分配”在这里是错的

很多人看到 m 个水龙头，第一反应是“把 w 排序，然后轮流分给 m 个龙头，让每个龙头的总和尽量均衡”。这个思路在某些调度问题里确实成立，但在这道题里是错的，原因就两条。

第一，人的顺序不能动。输入给的是一个固定序列，排在前面的人就是先来的，你不能把后面那个接水时间短的人提到前面去。这不是一个“自由分配任务给机器”的问题，而是一个“先到先服务，来了就往空位补”的问题。

第二，“让 m 个龙头尽量均衡”这个优化目标本身也不对。我们要最小化的是全部完成的时间，也就是最后一个龙头的完成时刻。尽量均衡确实有助于压低最大值，但在这个“顺序固定、先到先补”的约束下，正确的策略不是预先分配，而是在线地把每个人丢给当前最早空出来的龙头。

顺便说一句，“尽量均衡”这个方向在另一类问题里是对的工具，比如把一堆任务分给 m 台机器、任务顺序可以任意调整、目标是让最大负载最小，那属于多路划分问题，是个 NP 难问题的近似问题，常用 LPT（最长处理时间优先）这类启发式。但那是另一道题了，别混进来。

4.2 堆里存的到底是什么

先把状态定义清楚，这是模拟类题目最要紧的一步。设一个小根堆，堆里存的是m 个龙头各自的“空闲时刻”。

最开始，前 m 个人直接占据了 m 个龙头（如果 n < m 就所有人都能直接上），所以把前面 m 个人的 w 值全部压进堆里。堆里每个数字的含义是：这个龙头到那个时刻就会空出来。

接下来处理剩下的人。对第 i 个人（i ≥ m）：

1. 从堆顶取出最小的值 t，它代表最早空出来的那个龙头在 t 时刻就绪。
2. 这个人从 t 时刻开始接水，接完的时刻是 t + w[i]。
3. 把这个新时刻 t + w[i] 压回堆里。

一遍扫完之后，堆里剩下的 m 个数字就是 m 个龙头各自的最终完成时刻，取最大值就是答案。

这个循环的核心在于：堆顶永远给出当前时间线上最早的那个空闲点，我们不做任何“智能”决策，就是老老实实把下一个人挂上去。这就是这道题贪心的全部内容——它贪的是“局部上选择最早可用的资源”，而由于人的顺序固定，这种贪心不需要证明其全局最优性，它就是在描述规则本身，模拟出来的结果就是唯一的正确答案。

4.3 逐秒模拟和堆模拟：性能差了不止一个量级

同样能出正确答案的还有一种写法：开一个长度 m 的数组记录每个龙头剩余的工作量，然后一秒一秒地推进时间，每秒把每个还在工作的龙头的剩余量减一，减到 0 的立刻从队伍里拉下一个人进来。这个写法很好理解，代码也不长。

它的复杂度是 O(T · m)，其中 T 是最终答案的时间。在原题的数据范围内（n 不超过一万、m 不超过一百、每个人接水量不超过一百），T 大概在一万左右，T · m 大约是一百万次操作，跑起来完全没问题，很多人的第一版就是这么过的。

但换个数据范围就崩了。假设 n = 10^5、m = 10^3、每个人的接水量还是 100，那么 T 大约在 10^4 量级，T · m = 10^7，勉强还能跑。要是接水量放大到 10^6 呢？T 直接变成 10^8，乘上 m 就是 10^11，必死无疑。

堆模拟的复杂度是 O(n log m)。每个人一次出堆一次入堆，堆的大小始终是 m，所以每个人都只花 log m 的时间。上面那个极端数据下，n = 10^5、m = 10^3，总操作数是 10^5 × 10 ≈ 10^6，毫无压力。这就是数据结构对复杂度的降维打击。

有个更本质的区别：逐秒模拟的时间复杂度里带着 T 这个“值的量级”，而堆模拟的复杂度只跟“元素的个数”有关。凡是题目里的数值可以很大、但元素个数相对小的场景，都应该往堆这个方向想。

4.4 完整代码加一次手算验证

C++ 实现：

#include <bits/stdc++.h> using namespace std; int main() { int n, m; if (scanf("%d %d", &n, &m) != 2) return 0; vector<int> w(n); for (int i = 0; i < n; ++i) scanf("%d", &w[i]); priority_queue<int, vector<int>, greater<int>> pq; int k = min(n, m); for (int i = 0; i < k; ++i) pq.push(w[i]); for (int i = k; i < n; ++i) { int t = pq.top(); pq.pop(); pq.push(t + w[i]); } int ans = 0; while (!pq.empty()) { ans = max(ans, pq.top()); pq.pop(); } printf("%d\n", ans); return 0; }

先用一个小数据手动跑一遍，确认自己对流程的理解没错。取 n = 6、m = 2、w = [5, 3, 2, 4, 1, 6]。

初始堆：{5, 3}。

• 补第 3 个人，w = 2。取堆顶 3，压入 3 + 2 = 5，堆变成 {5, 5}。
• 补第 4 个人，w = 4。取堆顶 5，压入 5 + 4 = 9，堆变成 {5, 9}。
• 补第 5 个人，w = 1。取堆顶 5，压入 5 + 1 = 6，堆变成 {6, 9}。
• 补第 6 个人，w = 6。取堆顶 6，压入 6 + 6 = 12，堆变成 {9, 12}。

堆里最大值是 12，答案就是 12。

再用“人肉时间线”对一遍：t = 0 时，龙头甲接了 5 号（w=5），龙头乙接了 3 号（w=3）。t = 3 时乙先空，第 3 个人（w=2）上乙，t = 5 接完。t = 5 时甲空了（5 号在 t = 5 完成），第 4 个人（w=4）上甲，t = 9 接完；同一时刻乙也空了，第 5 个人（w=1）上乙，t = 6 接完。t = 6 时乙空，第 6 个人（w=6）上乙，t = 12 接完。t = 9 时甲空但没人了。最终 12。两条路径完全吻合。

Python 实现：

import heapq def total_time(w, m): heap = w[:m] heapq.heapify(heap) for x in w[m:]: t = heapq.heappop(heap) heapq.heappush(heap, t + x) return max(heap) if heap else 0

Python 版本的代码短得离谱，但逻辑和 C++ 完全一样。heapify 这一步比逐个 heappush 快，m 大的时候值得注意。

5. 堆的两个经典陷阱：大根堆和比较器

5.1 C++ 里 priority_queue 默认是大根堆

这是新手最容易翻车的地方。priority_queue<int>的堆顶是最大值，不是最小值。想用小根堆，必须把三个模板参数全写出来：

priority_queue<int, vector<int>, greater<int>> pq;

三个参数分别是：元素类型、底层容器、比较器。第三个参数 greater 表示“更大的元素优先级更低”，于是堆顶就成了最小值。少写一个参数编译不过，写错了方向则会在样例上直接暴露出答案偏大。

另一个常见错误是拿自定义类型放进优先队列，比较器写反了。比如用 pair：

// 按 first 从小到大 priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq; // 按 first 从大到小 priority_queue<pair<int,int>> pq;

greater<pair<int,int>>用的是 pair 的字典序比较，先比 first，first 相同再比 second。如果你的第二维有特殊含义（比如“同一时刻的龙头编号要小的优先”），这个默认行为可能正好符合，也可能正好反了，得看题目要求。

还有一种写法是自定义结构体重载运算符，要注意operator<的方向和直觉是反的：在priority_queue的默认比较器里，a < b为真表示 a 的优先级低于 b。我见过太多人在这一步写反，然后对着样例调半小时。

我的经验做法是：只要不是最简单的 int 小根堆，就一律写greater<类型>，或者干脆用emplace配一个 lambda 比较器（C++20 起可以直接传 lambda 给 priority_queue 的构造函数），少一层心算。实在不确定的时候，写三行代码测试一下：压入 1、3、2，看堆顶弹出的是不是 1。

5.2 Python 没有大根堆，只能靠取反

heapq只有小根堆。要当大根堆用，标准做法是压入的时候取负数，弹出之后再取反：

heapq.heappush(h, -x) largest = -heapq.heappop(h)

这里有个边界问题值得提前想清楚：如果 x 可能是 0，取反没影响；如果 x 是浮点数，负零和正零在比较上是相等的，也没问题；但如果 x 是无符号概念上的大整数，Python 的任意精度整数不受影响。所以 Python 里取反大法基本是安全的，唯一要小心的是别忘了弹出时再取反一次。

真正容易出问题的是用元组来同时维护多个优先级。假设你要按“完成时刻升序，完成时刻相同时按龙头编号升序”来出堆，代码看起来是这样：

heapq.heappush(h, (finish_time, tap_id))

这在充当小根堆的 heapq 里是对的，因为元组比较先比第一维再比第二维。但如果你用取反大法做成大根堆，写成(-finish_time, tap_id)，那么当两个完成时刻相同时，第二维会按 tab_id升序出堆，而不是你直觉里以为的“大的优先”。这类细节不算错，但如果你后面还有基于出堆顺序的逻辑，就得仔细确认它符不符合你的预期。

还有一个非常隐蔽的坑：元组里如果混进了不可比较的类型（比如第二维是 None 或者自定义对象），一旦出现第一维相同的情况，Python 就会去比第二维，然后直接抛 TypeError。调试的时候看到比较报错，先查这里。规避手段是在元组末尾加一个全局递增的计数器当作兜底：

counter = 0 heapq.heappush(h, (finish_time, counter, payload)) counter += 1

这样任何两个元素都不会在前两维完全相等，比较永远不会落到 payload 上。

5.3 手写二叉堆，竞赛里还值不值得写

先说结论：如果你能在 5 分钟内默写出一个正确的二叉堆，那就手写；否则老老实实用库。手写堆的价值不在于性能（STL 和 heapq 的常数因子已经很小了，手写一般不会更快），而在于这几种场景。

一是需要删除堆中任意元素，比如带懒删除的迪杰斯特拉，或者需要修改某个元素的键值。库里的优先队列都不支持这些操作，得自己维护。

二是需要同时拿到堆里的所有元素或者做堆排序。priority_queue不提供迭代器，你没法遍历它，只能一个个弹出，弹完就没了。如果既要在最后取最大值又不想破坏堆，得提前拷贝一份。

三是面试或者笔试的现场要求。有些场合明确要求手写堆，那你必须能写出来。

一份可靠的 C++ 最小堆实现：

struct MinHeap { vector<int> a; // a[0] 占位，下标从 1 开始 MinHeap() { a.push_back(0); } int size() const { return (int)a.size() - 1; } bool empty() const { return size() == 0; } int top() const { return a[1]; } void push(int x) { a.push_back(x); int i = size(); while (i > 1 && a[i] < a[i >> 1]) { swap(a[i], a[i >> 1]); i >>= 1; } } void pop() { if (empty()) return; a[1] = a.back(); a.pop_back(); int n = size(); int i = 1; while ((i << 1) <= n) { int l = i << 1, r = l + 1, s = l; if (r <= n && a[r] < a[l]) s = r; if (a[i] <= a[s]) break; swap(a[i], a[s]); i = s; } } };

下标从 1 开始是刻意的，这样父节点是 i>>1，左孩子是 i<<1，右孩子是 i<<1|1，全部是位运算，写起来快、也不容易算错。pop里那个if (empty()) return;的防御别省，尤其是当你在循环里 pop 的时候。

注意：用a[0]占位是常见写法，但如果你不小心在别处按 0 下标访问了 a，就会拿到那个占位值，导致很难查的逻辑错误。我习惯在调试阶段加一句 assert，把这类问题挡在前面。

6. 贪心能用在哪：和跳跃游戏 II 对照着看

6.1 跳跃游戏 II 的贪心是另一种形态

借这道题的热度顺便捋一下，同样是贪心，跳跃游戏 II 的贪心长得完全不一样。题面是：给一个非负整数数组 nums，你从下标 0 出发，nums[i] 表示从位置 i 最多能往前跳多少步，问跳到最后一个下标最少需要几步。

它的贪心做法不是排序，也不是模拟，而是区间推进：

int jump(vector<int>& nums) { int n = nums.size(); int end = 0, farthest = 0, steps = 0; for (int i = 0; i < n - 1; ++i) { farthest = max(farthest, i + nums[i]); if (i == end) { ++steps; end = farthest; } } return steps; }

核心逻辑是：在新的一跳所覆盖的整个区间里，找出下一步能到达的最远位置，等扫描到当前区间的右边界时，就消耗一跳、把边界推到那个最远位置。直观理解是“每一跳都尽量把落脚点选在能覆盖最远的那个位置”，这是一次全局性的区间扫描，而不是一次比较。

和接水问题对比一下就很清楚了。单水龙头接水题的贪心是交换论证型：结论是“小的排前面”，证明靠的是相邻两元素交换后目标函数的变化量，它本质上在给一个全序关系排序。多水龙头接水题的贪心是资源选择型：每一步都选当前最早可用的资源，几乎不需要证明，因为规则本身决定了它是在模拟一个确定的过程。跳跃游戏 II 的贪心是区间覆盖型：每一步都在一段可达范围里找刷新上界的位置，靠的是“可达范围”这个单调不减的性质。

三种形态的贪心，共同点是都不需要回头：做完一个决策之后，既不改也不撤销，一路推到结尾。

6.2 判断一道题能不能贪的三个信号

我在做题时，会用下面三条来快速判断一道题该不该往贪心上想。

第一个信号是目标函数能不能写成“每个元素贡献一个与位置有关的系数”的形式。像单水龙头接水的 W = Σ(n-j)·t[j]，形式上非常整齐，这种情况下排序加交换论证大概率有用。

第二个信号是决策之间会不会互相影响。如果每一步选完之后，后面的可选集合只是“缩小”而不会“变形”，那贪心是安全的。多水龙头就是这样：你选了一个龙头，它从可用集合里消失，但其他龙头的位置、属性都没变，后面的人面对的是同一个规则。反过来，如果选了一个东西会改变其他东西的权重，那贪心就危险了，得换成动态规划。

第三个信号是能不能找到反例。这需要一点直觉积累。做题的时候先在草稿纸上画三五个数，把贪心的结果和手动枚举的最优解对一下，能对上有戏，对不上立刻换方向。这个动作花不了一分钟，但能省掉半小时的无效编码。

6.3 0/1 背包反例：为什么单位价值排序会崩

最经典的“贪心为什么不行”的例子就是 0/1 背包。

假设背包容量是 10，有两个物品组：物品 A 重量 6、价值 7；物品 B 重量 5、价值 5；物品 C 重量 5、价值 5。

按单位价值排序：A 是 7/6 ≈ 1.167，B 和 C 都是 1.0。贪心会先拿 A，用掉 6 个单位，剩 4 个单位，B 和 C 都装不下了，总价值 7。而正确答案是拿 B 和 C，用满 10 个单位，总价值 10，明显更优。

崩掉的原因是：选 A 这个决策把剩余的容量改造成了“装不下 B 也装不下 C”的形态，后面的可选集合不仅缩小了，还变形成了一种对后续不利的形状。这就是 6.2 里第二条信号的负面案例。

有意思的是，如果把问题改成分数背包（物品可以切一部分拿走），那按单位价值排序就是严格最优的。所以在同一个问题背景下，一个微小约束的改动（能不能切分）就能决定贪心的生死。做题时把约束逐条读清楚，比什么技巧都重要。

回到接水问题，它是安全的，因为每个人是一个不可分割、必须完整服务、且服务时长固定的单位，人的顺序也不影响其他人的服务时长。这些条件正好避开了背包那种“决策改变后续形态”的陷阱。

7. 变体、数据规模与踩坑清单

7.1 带权等待时间：Smith 规则的引入

单水龙头那道题有个很自然的变体：每个人不仅有一个接水时长 t[i]，还有一个权重 w[i]（比如代表这个人的重要性），目标是让加权等待时间 Σ w[i] · (第 i 个人的等待时间) 最小。

这时候按 t[i] 排序就不一定对了，正确答案是按 t[i] / w[i] 从小到大排序。这条规则在调度理论里叫 Smith 规则，专门解决单机最小化加权完成时间之和的问题。

证明方法还是相邻交换。设相邻两个人里，前面那个是 (t1, w1)，后面那个是 (t2, w2)，前面所有人的总时长是 S。交换前这两人的加权等待时间贡献是 w1·S + w2·(S + t1)，交换后是 w2·S + w1·(S + t2)。两式相减，S 项消掉，只剩 w2·t1 - w1·t2。要让交换后更优，就要求 w2·t1 < w1·t2，即 t1/w1 < t2/w2。所以按 t/w 升序排就对了。

这个变体很有意思，因为它说明了一个道理：同一道题的贪心结论不是固定的，取决于目标函数长什么样。目标里加入了权重的维度，排序的 key 就要跟着变。写题的时候如果发现按 t 排序过不了，先回头看一眼目标函数里是不是多了什么系数。

顺带说一下，带权版本里如果 w[i] 不是整数而是有理数，为了避免浮点比较的精度问题，通常把比较写成t1 * w2 < t2 * w1的交叉相乘形式，全程整数运算。

7.2 数据范围和溢出，被卡过才知道疼

以下几个地方是我在比赛里真正被卡过的。

累加总和一定要用 64 位。单水龙头题的 W 上界大概是 O(n² · maxT)，n = 10^5、maxT = 10^4 的时候轻松突破 long long 吗？不会，但也远远超过 int 了，10^17 量级正好在 long long 的范围（约 9.2×10^18）之内。所以别犹豫，看到“总和”两个字就上 long long。

多水龙头题里，完成时刻的累加也可能溢出。单人最大接水量如果是 10^9、人数是 10^5，那最坏情况下串行累加能到 10^14，也是 int 装不下的量级。原题数据小不代表你遇到的所有版本数据都小，代码里把 int 换成 long long 的成本几乎为零。

数组下标越界是另一个高发区。多水龙头题的循环里，如果 n < m，那么“压前 m 个人”这一步就会越界。必须写成min(n, m)。如果 n = 0，那堆是空的，最后的取最大值那步要能安全处理空堆。

7.3 对拍和暴力验证的具体做法

写完一个贪心解之后，最大的风险是“样例过了，但结论其实是错的”。防这个风险最有效的手段是对拍：写一个保证正确但很慢的暴力解，随机生成小数据，两边跑，比对输出。

对单水龙头题，暴力解就是枚举所有排列，逐个算总等待时间取最小。n 取到 8 或者 9 就行，因为 9! = 362880，跑几千组数据也就几秒。

对多水龙头题，暴力解就是 4.3 里说的逐秒模拟。这个实现简单，出错的概率很低，正好用来当基准。

对拍的三个注意点。一是数据范围要小而全面：既要有 n 很小的、也要有 n 接近 m 的、还要有大量重复值的，重复值是最容易暴露“时间相同时的排序规则”问题的地方。二是比对要严格：不要只比最后那个数字，如果题目要求输出顺序，还要把顺序逐项比一遍。三是跑了多少组要打印出来，跑了一千组全过，心理上才踏实。

// 对拍的核心骨架：C++ 版 for (int iter = 1; iter <= 2000; ++iter) { system("./gen > in.txt"); system("./slow < in.txt > slow.out"); system("./fast < in.txt > fast.out"); if (system("diff slow.out fast.out > /dev/null")) { printf("WA on iteration %d\n", iter); break; } printf("ok %d\n", iter); }

在 Windows 上把 diff 换成 fc，路径分隔符换掉就行。这个模板我在很长一段时间里是直接放在桌面上的，遇到结论拿不准的贪心题就套一次。

7.4 收尾前再说两个小经验

第一个经验是关于读题的。接水类题目往往有一句话决定了整个解法，比如“按给定顺序”这四个字。我的习惯是把题面里所有描述约束的短句抄到草稿纸上，一条条对着写解法，确认每一条约束都在这套解法里被尊重了。这个动作大概花两分钟，能省下大量返工。

第二个经验是关于代码风格的。接水这类模拟题、堆题，变量名一定要起得能读出含义：free_time比t好，tap_finish比f好，waiting_total比sum好。因为堆题的 bug 大多藏在“我到底往堆里存了什么”这个语义层面，而不是语法层面，变量名就是你的记忆锚点。等代码写到第三十行再回头看，t + w[i]到底代表什么，只有清晰的命名能告诉你。

最后再补一句关于贪心心态的体会。贪心的题做多了会产生一种错觉，觉得什么题都能“想一想就出来”。实际上真正卡的从来不是想出那个结论，而是证明那个结论。养成每写一个贪心就先在心里过一遍交换论证或者区间不变量的习惯，时间长了，很多题的结论会自己浮出来，而且浮出来的结论大概率是对的。