接水问题这个名字听起来像是一道小学数学应用题但只要把它扔进算法题库里它就会立刻变成贪心算法里最有代表性的入门题型之一。我自己第一次见到它是在刷排队类的模拟题时当时以为只要把人按顺序塞进去就行结果提交上去一半的测试点全红。后来才明白接水问题的核心根本不在模拟而在排序和调度也就是贪心算法最朴素的两个动作先处理谁以及空闲资源给谁。这篇文章我想把这类题目彻底讲透从单水龙头的排队接水到多水龙头的并行调度把公式推导、代码实现、复杂度分析、踩坑经验一次说清楚。如果你刚开始接触贪心算法或者在洛谷、力扣上被这类题卡住过那这篇内容会帮你把思路理顺如果你已经能写出来那里面关于交换论证和优先队列的部分也能让你对贪心的正确性有更扎实的理解。1. 接水问题的两个版本先搞清楚要解决哪一个很多人拿到接水问题这四个字就急着写代码其实这个标题下面藏着两个完全不同的模型。它们长得像但解法方向差得很远。分不清版本写出来的代码大概率只能过一部分样例。我在带新人刷题的时候第一步永远是让他们先回答一个问题这题的水龙头有几个人的顺序能不能改。1.1 单龙头排队让平均等待时间最短第一个版本我习惯叫排队接水。场景是这样的只有一个水龙头有 n 个人等着接水每个人接水需要的时间各不相同比如有人打一杯水要 2 分钟有人要 5 分钟。现在你可以自由安排这 n 个人的接水顺序目标是让所有人的平均等待时间最小。这里的等待时间要特别注意指的是每个人从开始排队到轮到自己接水之间的那段空等时间不包括自己接水的时长。第一个人等待时间是 0第二个人要等第一个人接完第三个人要等前两个人接完以此类推。这个版本的关键就在于顺序可变。正因为顺序可以自由调整才有了贪心算法发挥的空间。如果我们把接水时间短的人排在前面后面的人等待的基数就小整体平均等待时间自然被压下来。这就是典型的短作业优先思想在操作系统调度里叫 SJF在算法题里就是最基础的排序贪心。这个版本几乎就是为贪心算法量身设计的。你不需要模拟时间流逝不需要维护任何队列只要排序加一次遍历求和就能出答案代码量极小但背后的推导却值得反复琢磨。洛谷上的 P1223 排队接水就是它的标准形态。1.2 多龙头并行让最后一个人尽早接完第二个版本我习惯叫多龙头调度。场景变成有 m 个水龙头同时开放n 个人依次来接水有的题目规定顺序固定按编号来每个人接水时间给定。人到了之后如果水龙头有空就立刻用全满就得等等到有龙头空出来再上。这个版本的目标通常是最小化总完成时间也就是最后一个人接完水的那个时刻。注意这里的人往往不能随意插队因为题目规定的是按编号顺序到达你只能决定下一个到的人分配到哪个已经空出来的龙头。所以它更像一道模拟题但模拟的过程中用到一个贪心策略每次把新来的这个人交给当前最早能空出来的那个水龙头。这个策略听上去理所当然但它需要一个合适的数据结构来高效维护最早空出来的龙头答案就是小顶堆也就是优先队列。用堆维护每个龙头当前累计到的时间堆顶永远是那个累计时间最小的龙头谁最小就把下一个人给谁。整个过程既像模拟又带着贪心的味道。两个版本对照起来看第一个版本考的是排序方向对不对第二个版本考的是资源分配策略对不对。前者偏数学和证明后者偏数据结构和模拟。很多人混淆的根源就是把第一个版本的排序结论套到了第二个版本上结果发现样例都过不了。提示拿到接水类题目先看两件事——水龙头数量是否为 1以及人的顺序是否允许重排。这两个条件决定了你该走排序贪心还是优先队列模拟。弄清版本差异之后后面的事情就好办了。第一类问题我们重点解决为什么这样排序最优第二类问题我们重点解决优先队列怎么维护。两条线分开走思路反而更清楚。2. 排序贪心的正确性为什么慢的人往后排是最优写出排序代码其实只要三行但真正有价值的是搞清楚为什么这么排。贪心算法最怕的就是看着像对的一旦遇到变形题或者数据范围变化没有正确性支撑的直觉很容易翻车。接水问题的好处是它的正确性可以用两种方式讲得明明白白一个靠公式一个靠交换论证。2.1 从总等待时间公式看排序方向先设 n 个人的接水时间分别是 t1, t2, ..., tn我们排好一个顺序叫 p1, p2, ..., pn。那么每个人的等待时间可以写出来排在第一位的人等待 0第二位等待 t 的 p1第三位等待 p1p2 的接水时间之和一直到最后一位等待前面所有人的时间之和。如果我们把总等待时间看成每个人等待时间相加那么第 j 个人位置在 j的等待时间其实就是前面 j-1 个人接水时间的加总。把所有等待时间加起来你会得到一个非常漂亮的结论每个人的接水时间 t会被它后面的人各等待一次。换句话说如果某个人排在位置 j他的接水时间 t 会被后面 n-j 个人各等一次于是他在总等待时间里的贡献值就是 (n-j) 乘以 t。这个视角一换问题立刻清晰了。总等待时间等于每个接水时间乘以它对应的系数再求和。排在最前面的人系数最大是 n-1排在最后面的人系数最小是 0。既然我们要让总和最小那就应该让系数大的位置放小的 t系数小的位置放大的 t。翻译成人话就是接水快的人往前站接水慢的人往后站。这就是排序贪心的全部逻辑一句话总结谁接水时间短谁先上。你可能觉得这太简单了但正是这种直观结论 严格推导的组合才是贪心算法最标准的解题姿态。很多难题的贪心部分最终也是落脚到某个量应该按什么序排这个问题上。2.2 交换论证一句话把贪心策略钉死公式推导已经很有说服力了不过还有一种更利落的证明方式叫交换论证。它的思路是假设存在一个最优解如果这个最优解里有两相邻的人前面那个接水时间反而比后面那个人更长那我们把他们俩换一下位置总等待时间一定会变小。具体推一下。设这两个相邻的人前面所有人的接水时间总和是 W也就是说轮到这两个人时已经过去的时间是 W。原来是 a 在前、b 在后a 的等待时间是 Wb 的等待时间是 W 加上 a 的接水时间。两个人贡献的等待时间加起来是 2W 加上 a 的时间。交换之后b 在前、a 在后b 的等待时间是 Wa 的等待时间是 W 加上 b 的时间。两个人贡献变成 2W 加上 b 的时间。因为 a 的接水时间比 b 长交换后这个局部贡献变小了也就是说原来的解不是最优的矛盾。于是结论成立任何一个最优解里都不可能出现前面慢、后面快的相邻对。把这句话推而广之最优解必然是整体按接水时间非递减排列。交换论证的好处是它不需要你写出完整的总和公式只盯着相邻两人的局部就能得出全局结论特别适合在面试或者写题解时用来快速论证。我自己在复习贪心时会把交换论证当成一个固定套路记下来。只要题目问的是如何排序使某个总量最小或最大我就会尝试构造一个相邻交换看换完之后目标函数是变大还是变小。能试出来贪心的方向就确定了。2.3 边界与坑点排序之外的细节策略确立之后剩下的是实现层面的坑。第一个坑是等待时间的定义有些题问的是平均等待时间有些问的是所有人接完水的总耗时这两个完全不是一回事。总耗时是从第一个人开始到最后一个人接完等于所有人接水时间的总和跟你怎么排无关而平均等待时间才和顺序有关。题目问哪个你就算哪个别想当然。第二个坑是输出格式。排队接水类题目经常要求你输出最优的排队顺序也就是每个人的原始编号而不仅仅是时间。这时候排序时不能只排时间数组得把下标一起带上排序后输出对应的编号序列。我见过不少人只排了时间输出了一串时间值结果格式错误。第三个坑是相同时间的处理。当两个人接水时间一样时先排谁都可以总等待时间不变。但如果题目要求输出字典序最小的方案那相同时间就要按原始编号小的排前面。这种细节不写清楚评测机照样给你判错。做法很简单排序的比较函数里加一个时间相同时按编号升序的兜底条件就行。注意数据范围大时总等待时间会超过 32 位整数上限。n 到十万级别、单次接水时间到一万级别时总等待时间的量级能到 10 的 15 次方必须用 64 位整数Python 虽然不用操心但 C 里 long long 别省。3. 代码落地单龙头排队接水的完整实现原理讲完了接下来是能直接抄的部分。我把单龙头排队接水的实现分成两步第一步排序并记录编号第二步遍历累加等待时间。整个过程是线性的复杂度由排序决定。这里我会给 Python 和 C 两个版本并配一组可以手工验证的测试数据。3.1 Python 实现与逐行注释Python 写这类题特别顺手因为排序和累加都很简洁。下面这段代码同时算出了总等待时间和平均等待时间还保留了最优顺序。def queue_water(times): n len(times) # 把 (接水时间, 原始编号) 打包后排序编号从 1 开始 people sorted([(t, i 1) for i, t in enumerate(times)]) total_wait 0 current 0 # 当前已经流逝的时间 order [] for t, idx in people: total_wait current # 这个人的等待时间 current t # 接完水时间往后推 order.append(idx) avg total_wait / n return order, total_wait, avg这里有几个细节值得说。sorted对元组排序时默认先比第一个元素接水时间时间相同才比第二个元素编号正好满足时间相同按编号升序的要求不需要额外写比较函数。current维护的是到目前为止累计过去的时间轮到某个人时他等待的就是这个current接完后再把current加上他自己的接水时间。如果你要输出总等待时间直接返回total_wait。如果题目要求保留两位小数输出平均等待时间用格式化字符串处理即可。注意别在累加过程中做除法浮点误差会累积最后统一除一次最稳。3.2 C 实现与注意事项C 版本的重点是选对数据类型和排序方式。用结构体或者 pair 都可以pair 更省事默认也按第一关键字排序。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairlong long, int a(n); for (int i 0; i n; i) { long long t; cin t; a[i] {t, i 1}; // 时间, 编号 } sort(a.begin(), a.end()); // 时间升序时间相同编号升序 long long total 0, cur 0; for (auto p : a) { total cur; // 累加等待时间 cur p.first; // 推进当前时间 cout p.second ; } cout \n; printf(%.2f\n, (double)total / n); return 0; }total和cur都用了long long就是为了防止溢出。sort对pair的默认行为是先按first升序first相等时按second升序正好符合要求。输出顺序时直接打印每个 pair 的编号即可。用printf控制小数位比cout加fixed更直接。这里有一个容易忽略的点如果题目只要求输出平均等待时间那顺序就不重要可以省掉编号直接对时间数组排序。但如果你要输出排队方案编号必须全程带着。我在实际写的时候习惯一律带上编号多占一点内存换来的代码通用性很划算。3.3 测试用例与手工验证光看代码没有体感我们拿一组数据手工跑一遍。假设有 5 个人接水时间分别是 5、3、8、1、4。按升序排完之后是1、3、4、5、8对应原始编号是 4、2、5、1、3。逐个累加等待时间第一个人等 0第二个人等 1第三个人等 4第四个人等 8第五个人等 13。总等待时间是 014813 26平均等待时间 26/5 5.2。如果反过来按降序排8、5、4、3、1等待时间分别是 0、8、13、17、20总等待时间 58平均 11.6。同样的五个人仅仅换了个顺序平均等待时间从 5.2 涨到 11.6翻了一倍还多。这就是排序贪心的威力也解释了为什么它的推导值得认真看。你可以把上面这段代码粘到本地跑一下输入这五个数字看输出是不是 26 和 5.20。能对上说明实现没问题。如果对不上八成是等待时间的累加时机搞错了检查一下是先累加再推进还是先推进再累加顺序反了结果完全不同。提示等待时间的累加一定要在cur更新之前完成。如果把cur t写在total cur前面每个人都会多算一次自己的接水时间结果整体偏大。4. 多龙头并行接水优先队列贪心的正确打开方式单龙头的问题解决之后多龙头版本就登场了。这个版本的难度上了一个台阶因为它不再是一个纯粹的排序问题而变成了一个带时间推进的资源分配问题。核心矛盾是当多个人同时争抢有限的几个水龙头时应该把下一个位置分配给哪个龙头。4.1 模拟思路与数据结构选择先把场景想清楚。假设有 m 个水龙头n 个人按某种顺序依次到来。每个人一到如果他面前有空闲的龙头立刻就用如果所有龙头都在忙他就只能等等到其中一个龙头空出来。整个过程的时间推进是连续的但因为我们只关心每个人什么时候开始、什么时候结束所以可以用一个龙头当前的可用时刻来刻画状态。每个龙头都有一个空闲下来的时间点初始都是 0一开始全都空着。来了一个人他的接水时间是 t我们把他分配给当前空闲时间最早的龙头那么他会在那个龙头的空闲时刻开始接水接完之后这个龙头的新空闲时刻就变成了原来空闲时刻加上 t。最终所有龙头空闲时刻的最大值就是这个调度方案的总完成时间。问题来了怎么高效地找出空闲时刻最小的龙头最朴素的做法是每次遍历所有龙头找最小值复杂度是 n 乘 m。当 n 和 m 都到十万级别时这个乘起来就是十的十次方直接超时。这时候就轮到小顶堆出场了。4.2 小顶堆实现与复杂度分析小顶堆的性质是堆顶永远是最小值取出堆顶和插入新元素都是对数复杂度。我们把每个龙头的空闲时刻放进堆里每次来人时弹出堆顶把它加上这个人的接水时间再塞回去。这样每次操作是 O(log m)n 个人总共是 O(n log m)比暴力快了一个数量级。import heapq def multi_tap_total(times, m): if m len(times): return max(times) if times else 0 # 初始化 m 个龙头空闲时刻均为 0 heap [0] * m heapq.heapify(heap) for t in times: free_at heapq.heappop(heap) # 最早空闲的龙头 heapq.heappush(heap, free_at t) return max(heap)代码非常短但逻辑很严密。heappop拿出的永远是当前空闲时间最小的那个龙头把新的人安排给它符合谁先空谁接活的贪心策略。循环结束后堆里存的是所有龙头各自的空闲时刻取最大值就是全部接完的时间。对于顺序固定的版本这个算法直接就是答案。如果题目允许重排顺序也就是你可以决定谁先接那么为了让总完成时间尽可能小通常会采用最长的任务优先策略也就是把接水时间最长的人先安排给最空闲的龙头。这个策略叫做 LPT直觉上能平衡各个龙头的负载减小最大值但它不保证绝对最优只是近似效果好。这类多机调度问题在理论上属于较难的问题比赛里出现的通常都是顺序固定的模拟版本所以优先队列这套写法覆盖了绝大多数场景。4.3 手工推演一个样例我们拿 3 个龙头和 5 个人来走一遍接水时间按到达顺序是 4、3、2、1、5。初始堆是 [0, 0, 0]。第一个人接水 4 分钟弹出空闲时刻 0塞回 044堆变成 [0, 0, 4]。第二个人接水 3 分钟弹出 0塞回 3堆变成 [0, 3, 4]。第三个人接水 2 分钟弹出 0塞回 2堆变成 [2, 3, 4]。第四个人接水 1 分钟弹出 2塞回 3堆变成 [3, 3, 4]。第五个人接水 5 分钟弹出 3塞回 8堆变成 [3, 4, 8]。最后取堆中最大值 8就是总完成时间。你可以自己拿笔画一下时间轴三个龙头从 0 时刻开始分别接了 4、3、2 分钟的任务之后第四个和第五个人依次补位最后一个人 5 分钟的活从时刻 3 开始到时刻 8 结束。跟堆算出来的结果一致。这组数据里第三个龙头空闲时刻一直是 4第五个人到来时堆顶已经是 3 了所以给到了另一个龙头。这种动态看谁先空的分配纯靠人脑模拟很容易乱用堆来维护就一目了然。注意如果某道题里 m 大于等于人数那每个人都能分到独立龙头总完成时间就是所有人接水时间的最大值。这种情况下堆依然能算对只不过每个元素都只被用过一次堆顶一直是 0。5. 贪心思维的迁移和跳跃游戏2的异同接水问题练熟之后你可能会发现网上很多贪心算法的文章都会同时提到跳跃游戏2。这两个题看起来八竿子打不着一个讲接水排队一个讲数组跳跃但它们其实是贪心算法里两种典型范式的代表放在一起对比能帮你把贪心的思维框架搭得更完整。5.1 跳跃游戏2的贪心内核跳跃游戏2的题目大意是给你一个非负整数数组每个元素表示你在这个位置最多能往前跳几步你从数组第一个位置出发问到达最后一个位置最少需要跳几次。它的贪心策略是维护一个当前能到达的最远位置以及一个当前这一步的边界。每次在边界内扫描更新最远能到的地方一旦走到边界就说明必须再跳一次于是跳跃次数加一把边界更新为当前最远可达位置。这个贪心里面最关键的一句是在不得不跳之前尽量跳得最远。它和接水问题的共同点在于两者都是在每一步做一个局部看起来最合理的选择并且都依赖某种单调性来保证局部最优能推出全局最优。接水问题的单调性是接水时间短的人越靠前后面等待的人越少跳跃游戏的单调性是能跳得更远的位置一定不会比跳得近的位置差。区别在于接水问题的贪心落在排序上一旦排好顺序整个方案就确定了是一种一次性的决策而跳跃游戏的贪心是边走边决策的每一步都要根据当前扫描范围动态更新属于过程式贪心。这两类贪心在题目里都非常常见前者叫排序贪心后者常被称为范围贪心或者区间贪心。5.2 两类贪心的共同点与识别方法把这两个题放在一起我能总结出一条识别贪心的粗略经验当题目里出现如何安排顺序让某个总量最优时多半是排序贪心当题目里出现每步能走多远、每次能覆盖多大范围、问最少多少步时多半是范围贪心。接水问题属于前者跳跃游戏2属于后者。它们更深层的共通点是局部最优的可保持性。接水问题里把最快的人放前面不会破坏后面任何一步的最优性因为我们用的是交换论证证明了全局最优的结构就是升序。跳跃游戏里在边界内选出能跳最远的位置不会让后续需要跳的次数变多因为覆盖范围是单调不减的。判断一道题能不能用贪心本质就是判断这个不破环的性质成不成立。我在刷题时会做一个小练习每遇到一道贪心题先问自己它是不是在决定顺序如果不是再问它是不是在维护一个当前最优的边界或极值。这两问能覆盖大部分入门到中等的贪心题。接水问题和跳跃游戏2正好是这两个问题的标准答案所以它们总被一起提起。提示贪心算法的正确性从来不是感觉对了就行。能用交换论证证明的就写清楚证明不了的要么换动态规划要么找反例。接水问题的价值就在于它是一个能用严格证明拿下的贪心样板。6. 常见问题与排查技巧实录写了这么多最后落回到实操。接水类的题目在评测时出错原因其实就那么几类我把它们整理成表格方便你对照排查。这些都是我自己和身边人真金白银踩出来的。6.1 问题速查表现象可能原因排查与解决部分测试点答案偏大等待时间累加时机错误确认是先累加等待时间再推进当前时间顺序不能反大范围数据结果溢出用了 32 位整数总和改用 64 位整数Python 无此问题输出格式错误只排了时间没带编号排序时把下标一起打包输出原始编号序列多龙头结果偏小堆初始化数量不足确认初始化了 m 个 0m 小于人数时才需要堆平均等待时间精度不够累加过程中做了除法全程用整数累加最后统一除以人数相同时间顺序不对缺少编号兜底比较排序键设为 (时间, 编号)保证字典序最小表格里的每一条我都遇到过至少一次。其中等待时间累加时机是最隐蔽的因为样例数据小的时候两种写法可能碰巧结果一样只有数据一大才暴露所以一定要养成先看累加逻辑的习惯。6.2 几个容易忽略的实操细节第一个细节是空输入和单元素输入。有些题目的数据范围允许 n 为 0 或者 1这时候排序、堆、取最大值都要做相应处理。多龙头版本里如果人数为 0直接返回 0如果龙头数大于等于人数可以直接返回所有人接水时间的最大值省掉建堆的开销。第二个细节是堆的初始值。多龙头问题里每个龙头一开始都是空闲的所以初始放入 m 个 0。我见过有人初始化成 m 个正无穷结果每次弹出来都是无穷整个调度完全错乱。空头的语义是这个龙头从第 0 时刻起就可用一定是 0不是其他数。第三个细节是输出顺序的编号。排队接水题要求输出最优排队序列时编号通常从 1 开始而不是数组下标 0。打包排序的时候记得给编号加一否则评测机看到从 0 开始的编号会直接判错。这个坑新手里十个有八个会踩。如果你还想继续深入我的建议是拿几道变形题练手比如让每个人接水时间不再是定值而是随机的、比如龙头有维修时间、比如要求输出字典序最小的方案。这些变体不会改变贪心的内核但会逼着你想清楚每一处细节的边界条件。把接水问题和跳跃游戏2这两类贪心都吃透再去看其他贪心题基本都能找到熟悉的影子。