企业官网建设流程全解析

接水问题这个名字听起来像是一道小学数学应用题，但只要把它扔进算法题库里，它就会立刻变成贪心算法里最有代表性的入门题型之一。我自己第一次见到它是在刷排队类的模拟题时，当时以为只要把人按顺序塞进去就行，结果提交上去一半的测试点全红。后来才明白，接水问题的核心根本不在"模拟"，而在"排序"和"调度"，也就是贪心算法最朴素的两个动作：先处理谁，以及空闲资源给谁。这篇文章我想把这类题目彻底讲透，从单水龙头的排队接水，到多水龙头的并行调度，把公式推导、代码实现、复杂度分析、踩坑经验一次说清楚。如果你刚开始接触贪心算法，或者在洛谷、力扣上被这类题卡住过，那这篇内容会帮你把思路理顺；如果你已经能写出来，那里面关于交换论证和优先队列的部分，也能让你对贪心的正确性有更扎实的理解。

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，第三位等待 p1+p2 的接水时间之和，一直到最后一位等待前面所有人的时间之和。

如果我们把"总等待时间"看成每个人等待时间相加，那么第 j 个人（位置在 j）的等待时间，其实就是前面 j-1 个人接水时间的加总。把所有等待时间加起来，你会得到一个非常漂亮的结论：每个人的接水时间 t，会被它后面的人各等待一次。换句话说，如果某个人排在位置 j，他的接水时间 t 会被后面 n-j 个人各等一次，于是他在总等待时间里的"贡献值"就是 (n-j) 乘以 t。

这个视角一换，问题立刻清晰了。总等待时间等于每个接水时间乘以它对应的系数再求和。排在最前面的人系数最大，是 n-1；排在最后面的人系数最小，是 0。既然我们要让总和最小，那就应该让系数大的位置放小的 t，系数小的位置放大的 t。翻译成人话就是：接水快的人往前站，接水慢的人往后站。

这就是排序贪心的全部逻辑，一句话总结：谁接水时间短，谁先上。你可能觉得这太简单了，但正是这种"直观结论 + 严格推导"的组合，才是贪心算法最标准的解题姿态。很多难题的贪心部分，最终也是落脚到"某个量应该按什么序排"这个问题上。

2.2 交换论证：一句话把贪心策略钉死

公式推导已经很有说服力了，不过还有一种更利落的证明方式，叫交换论证。它的思路是：假设存在一个最优解，如果这个最优解里有两相邻的人，前面那个接水时间反而比后面那个人更长，那我们把他们俩换一下位置，总等待时间一定会变小。

具体推一下。设这两个相邻的人前面所有人的接水时间总和是 W，也就是说轮到这两个人时，已经过去的时间是 W。原来是 a 在前、b 在后，a 的等待时间是 W，b 的等待时间是 W 加上 a 的接水时间。两个人贡献的等待时间加起来是 2W 加上 a 的时间。

交换之后，b 在前、a 在后，b 的等待时间是 W，a 的等待时间是 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; vector<pair<long 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。总等待时间是 0+1+4+8+13 = 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，塞回 0+4=4，堆变成 [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 问题速查表

表格里的每一条我都遇到过至少一次。其中"等待时间累加时机"是最隐蔽的，因为样例数据小的时候，两种写法可能碰巧结果一样，只有数据一大才暴露，所以一定要养成先看累加逻辑的习惯。

6.2 几个容易忽略的实操细节

第一个细节是空输入和单元素输入。有些题目的数据范围允许 n 为 0 或者 1，这时候排序、堆、取最大值都要做相应处理。多龙头版本里，如果人数为 0，直接返回 0；如果龙头数大于等于人数，可以直接返回所有人接水时间的最大值，省掉建堆的开销。

第二个细节是堆的初始值。多龙头问题里每个龙头一开始都是空闲的，所以初始放入 m 个 0。我见过有人初始化成 m 个正无穷，结果每次弹出来都是无穷，整个调度完全错乱。空头的语义是"这个龙头从第 0 时刻起就可用"，一定是 0，不是其他数。

第三个细节是输出顺序的编号。排队接水题要求输出最优排队序列时，编号通常从 1 开始，而不是数组下标 0。打包排序的时候记得给编号加一，否则评测机看到从 0 开始的编号会直接判错。这个坑新手里十个有八个会踩。

如果你还想继续深入，我的建议是拿几道变形题练手：比如让每个人接水时间不再是定值而是随机的、比如龙头有维修时间、比如要求输出字典序最小的方案。这些变体不会改变贪心的内核，但会逼着你想清楚每一处细节的边界条件。把接水问题和跳跃游戏2这两类贪心都吃透，再去看其他贪心题，基本都能找到熟悉的影子。