“接水问题”这个标题在题库里一搜能搜出好几道输入格式不一样模型不一样最优解也不一样但它们的标签上都写着“贪心算法”。我刚开始刷贪心专题的时候就是被这种同名不同题的命名坑过一次——看到“接水”两个字脑子里立刻蹦出“时间短的排前面”三段排序代码写完交上去评测机回了一排红。后来把题面逐字读了一遍才发现那道题里水龙头有 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 两道题的核心差异对照对比项单水龙头排队接水m 个水龙头接水可决策的量排队顺序下一个人补到哪个龙头人的顺序可以任意重排输入给定不可重排目标函数最小化平均总等待时间最小化全部完成的总时间核心方法排序 相邻交换证明小根堆模拟时间线时间复杂度O(n log n)O(n log m)易错点混淆等待时间与完成时间试图排序、堆的方向搞反把这张表记住比背十道题的代码都有用。看到“接水”两个字先问自己三个问题水龙头有几个人的顺序能不能动问的是平均等待时间还是总完成时间这三个问题的答案组合起来就能立刻定位到对应的解法。2. 相邻交换法把“小的排前面”从直觉变成证明2.1 总等待时间可以改写成一个更友好的求和式设某个排队顺序为 t[1], t[2], ..., t[n]下标表示他们接水的先后位置。第 k 个人前面有 k-1 个人他要等的时间就是这 k-1 个人的接水时长之和。所有人的等待时间总和 W 写成W Σ(k1..n) Σ(j1..k-1) t[j]这个双重求和看着不友好但换个角度数一下就能化简。我们要数的是每个 t[j] 被加了多少次——t[j] 位于第 j 个位置它的后面有 n-j 个人这 n-j 个人每个人等待时都会把 t[j] 算进去一次所以W Σ(j1..n) (n-j) · t[j]这一步是整个证明的地基。它的直观含义是位置越靠前的人他的接水时长被越多的人等待。排在第 1 位的那个人他的 t 被后面 n-1 个人等排在最后一位的人他的 t 一次都不会被别人等。所以越大的系数越应该配越小的 t这就是“小的排前面”的全部秘密。2.2 交换相邻两个人看总等待时间怎么变现在假设有一个排队顺序其中有相邻的两个人位置分别是 i 和 i1接水时长分别记为 x t[i] 和 y t[i1]。我们只把这两个人换一下位置其他人的位置完全不动。先看这两个人在位置 i 和 i1 上的贡献。根据上面的公式位置 i 的系数是 n-i位置 i1 的系数是 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[i1]也就是一个逆序对。把这两个相邻的人换过来总等待时间严格变小。第二步重复做这件事每换一次逆序对就少一个队列里的逆序对总数是有限的最终一定会停在一个没有任何逆序对的排列上——那就是升序排列。而升序排列已经不可能通过任何相邻交换再变小了因为任意相邻两个都满足 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 要输出原始编号时怎么处理如果题目还要求输出排队顺序的编号那就不能在排序的时候把编号弄丢。两个常用做法。做法一排序下标数组vectorint 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);做法二直接用 pairvectorpairint,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; vectorpairint,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), keylambda 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从堆顶取出最小的值 t它代表最早空出来的那个龙头在 t 时刻就绪。这个人从 t 时刻开始接水接完的时刻是 t w[i]。把这个新时刻 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; vectorint w(n); for (int i 0; i n; i) scanf(%d, w[i]); priority_queueint, vectorint, greaterint 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 号w5龙头乙接了 3 号w3。t 3 时乙先空第 3 个人w2上乙t 5 接完。t 5 时甲空了5 号在 t 5 完成第 4 个人w4上甲t 9 接完同一时刻乙也空了第 5 个人w1上乙t 6 接完。t 6 时乙空第 6 个人w6上乙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 0Python 版本的代码短得离谱但逻辑和 C 完全一样。heapify 这一步比逐个 heappush 快m 大的时候值得注意。5. 堆的两个经典陷阱大根堆和比较器5.1 C 里 priority_queue 默认是大根堆这是新手最容易翻车的地方。priority_queueint的堆顶是最大值不是最小值。想用小根堆必须把三个模板参数全写出来priority_queueint, vectorint, greaterint pq;三个参数分别是元素类型、底层容器、比较器。第三个参数 greater 表示“更大的元素优先级更低”于是堆顶就成了最小值。少写一个参数编译不过写错了方向则会在样例上直接暴露出答案偏大。另一个常见错误是拿自定义类型放进优先队列比较器写反了。比如用 pair// 按 first 从小到大 priority_queuepairint,int, vectorpairint,int, greaterpairint,int pq; // 按 first 从大到小 priority_queuepairint,int pq;greaterpairint,int用的是 pair 的字典序比较先比 firstfirst 相同再比 second。如果你的第二维有特殊含义比如“同一时刻的龙头编号要小的优先”这个默认行为可能正好符合也可能正好反了得看题目要求。还有一种写法是自定义结构体重载运算符要注意operator的方向和直觉是反的在priority_queue的默认比较器里a b为真表示 a 的优先级低于 b。我见过太多人在这一步写反然后对着样例调半小时。我的经验做法是只要不是最简单的 int 小根堆就一律写greater类型或者干脆用emplace配一个 lambda 比较器C20 起可以直接传 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 { vectorint 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 开始是刻意的这样父节点是 i1左孩子是 i1右孩子是 i1|1全部是位运算写起来快、也不容易算错。pop里那个if (empty()) return;的防御别省尤其是当你在循环里 pop 的时候。注意用a[0]占位是常见写法但如果你不小心在别处按 0 下标访问了 a就会拿到那个占位值导致很难查的逻辑错误。我习惯在调试阶段加一句 assert把这类问题挡在前面。6. 贪心能用在哪和跳跃游戏 II 对照着看6.1 跳跃游戏 II 的贪心是另一种形态借这道题的热度顺便捋一下同样是贪心跳跃游戏 II 的贪心长得完全不一样。题面是给一个非负整数数组 nums你从下标 0 出发nums[i] 表示从位置 i 最多能往前跳多少步问跳到最后一个下标最少需要几步。它的贪心做法不是排序也不是模拟而是区间推进int jump(vectorint 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.167B 和 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]到底代表什么只有清晰的命名能告诉你。最后再补一句关于贪心心态的体会。贪心的题做多了会产生一种错觉觉得什么题都能“想一想就出来”。实际上真正卡的从来不是想出那个结论而是证明那个结论。养成每写一个贪心就先在心里过一遍交换论证或者区间不变量的习惯时间长了很多题的结论会自己浮出来而且浮出来的结论大概率是对的。