前两天刷题群里有人发了条链接，问P1223 排队接水有没有什么通俗易懂的讲法。我当时回了句：这题你只要抓住一句话——让接水快的人先上，所有排队的人的总等待时间就越少。就是这么个直觉，但真正把它讲清楚、写对，还得拆开揉碎了看。
P1223 排队接水是很多人入门贪心算法的第一道题。题目描述很生活化：n个人在一个水龙头前排队接水，每个人接水耗费的时间已知，要求你给出一个排队顺序，让所有人的平均等待时间最短，并输出这个排队顺序以及对应的平均等待时间。题面看着简单，但里面藏着三个关键点：一是“等待时间”的定义，二是为什么贪心排序有效，三是怎么在排序后还能正确输出每个人的原始编号。这篇文章从题意、证明、代码实现到易错点，完整过一遍，希望能让刚接触贪心算法的朋友少走点弯路。
1. 先搞懂题在问什么：题意拆解与贪心直觉
1.1 “等待时间”到底算到哪一刻
第一次做这题的人，十有八九会栽在这个概念上。题目里的等待时间，指的是每个人从排在队伍开始，到轮到自己接水之前这段干等的时间，不包括自己接水的时间。
拿样例说明。n=4，四个人接水时间分别是1、2、3、4。如果按1、2、3、4的顺序排队：
- 第1个人等待0分钟，接水1分钟；
- 第2个人等了1分钟，接水2分钟；
- 第3个人等了1+2=3分钟，接水3分钟；
- 第4个人等了1+2+3=6分钟，接水4分钟。
所以总等待时间 = 0 + 1 + 3 + 6 = 10，平均等待时间 = 10 / 4 = 2.50。这个2.50就是题目样例输出。
如果你把“等待时间”理解成“从开始排队到接完水的总耗时”，那算出来的平均时间是 (1+3+6+10)/4 = 5.00，那就和题目的2.50对不上了。所以动手写程序之前，先把这个概念钉死：累加等待时间时，只累加轮到自己之前别人已用掉的时间。
这样题意就清晰了：平均等待时间最小，等价于总等待时间最小，也就是要安排一种顺序，让“每个位置之前所有人的接水时间之和”的总和尽可能小。
1.2 “短作业优先”的直觉到底怎么来的
这个结论其实大家生活里都有体感。食堂打饭，如果前面一个人磨磨蹭蹭点半天菜，后面所有人都在心里骂；超市结账，收银员一看有人购物车里堆成山，经常会引导只拿一瓶水的顾客去另一个窗口。让耗时短的人先办事，后面的人排队时间自然就短。
但这个直觉要严谨化，得靠经典的交换论证法，也叫邻项交换法。假设当前排队顺序里有两段：前面某些人的接水总时间我们已经确定了，叫S；紧接着是两个人A和B，他们接水时间分别是a和b；再往后还有一批人。
先看A在前、B在后这种顺序：
- A接水时，B要等a分钟，B后面的所有人也要多等a分钟；
- B接水时，B后面的人还要多等b分钟。
所以A和B这两个相邻位置，对总等待时间的贡献，主要体现在两个点上：
- 如果A先接水，B以及B后面的人都会因为A的时间a而等待；A自己前面的人已经确定了，不受影响。
- 如果B先接水，A以及A后面的人都会因为B的时间b而等待。
关键的差异在于A和B互相之间的等待。先A后B时，B多等a；先B后A时，A多等b。所以当a ≤ b时，也就是A接水更快，先A后B一定不会比先B后A差；反过来也一样。既然任意两个相邻的逆序对都能通过交换让总等待时间不变差，重复交换下去，最终序列一定可以变成耗时从小到大排列。
这就是贪心算法在这道题里的合法性证明。你不需要记住“短作业优先”这个名字，只需要记住这个交换思想，后面很多贪心题都要用它。
2. 核心实现部位：排序、累加与输出顺序
2.1 排序不能丢“编号”，用结构体或 pair 保存原始位置
不少人第二遍写这题还是WA，不是因为算法不对，而是因为输出错了。题目要求的输出有两行：第一行是最优排队顺序对应的原始编号，第二行是平均等待时间。
如果你只开一个数组，sort完就什么都找不回来了。正确做法是给每个人保留两个信息：接水时间、原始编号。
C++里最简单的写法是用一个结构体，或者直接用pair<int, int>。pair排序默认先比较第一个字段，再比较第二个字段，这种天然特性在这道题里特别合适：
pair<int, int> a[1005]; // first = 接水时间，second = 原始编号 sort(a + 1, a + n + 1);因为第一关键字是接水时间，所以排序后a[i].second就是第i个位置上的人原本的编号，直接输出就行。
这里还有个细节：如果两个人接水时间相同，题目没有强制要求谁先谁后，因为相同耗时的两个人无论谁排前面，对总等待时间的贡献是一样的。但如果你希望相同时间的人仍然按原始编号顺序输出，用pair也可以做到——当first相等时，pair会自动按second升序排；如果你用自定义结构体，就在比较函数里加一句“时间相等时按编号升序”。
struct Person { int t; // 接水时间 int id; // 原始编号 } p[1005]; bool cmp(Person x, Person y) { if (x.t != y.t) return x.t < y.t; return x.id < y.id; }2.2 累加总等待时间：加权写法比两层循环更不容易错
总等待时间有两种写法，我建议新手都掌握。
第一种是“前缀和累加”写法：从第二个位置开始，每个人等待的时间就是他所有前一个人的接水时间之和，把这些等待时间加起来。
long long sum = 0; // 总等待时间 long long prefix = 0; // 当前人之前已用掉的时间 for (int i = 1; i <= n; i++) { sum += prefix; // 当前人干等了 prefix 分钟 prefix += p[i].t; // 这个人开始接水后，队伍累积时间增加 }第二种是“加权”写法，更简洁也更能体现排序的效果：第1个人的接水时间会被排在后面的n-1个人等待，第2个人的被n-2个人等待，依此类推，最后一个人不会被任何人等待。
long long sum = 0; for (int i = 1; i <= n; i++) { sum += p[i].t * (n - i); }这两种写法算出的结果完全一样。写第二种时要注意，乘出来是long long级别的量，别拿int硬扛。
2.3 平均等待时间的浮点输出问题
累加完之后，平均等待时间是sum / (double)n，输出保留两位小数。
C++里用printf("%.2f\n", avg);是最省事的。如果你习惯用cout，加上#include <iomanip>后写cout << fixed << setprecision(2) << avg << endl;。
这里要特别提醒：sum必须是整数类型或浮点类型，但是除法时一定要把其中一个操作数转成double。如果写成sum / n，整数除以整数会直接砍掉小数部分，结果变成0.00，这种低级错误在评测环境里就是整道题全WA。
3. 完整代码与复杂度剖析
3.1 C++ 完整实现
#include <bits/stdc++.h> using namespace std; struct Person { int t; int id; } p[1005]; bool cmp(Person a, Person b) { if (a.t != b.t) return a.t < b.t; return a.id < b.id; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { cin >> p[i].t; p[i].id = i; } sort(p + 1, p + n + 1, cmp); long long sum = 0; long long prefix = 0; for (int i = 1; i <= n; i++) { sum += prefix; prefix += p[i].t; } for (int i = 1; i <= n; i++) { cout << p[i].id << (i == n ? "\n" : " "); } printf("%.2f\n", (double)sum / n); return 0; }代码本身不复杂，但有三行值得说。
p[i].id = i;这句是把读入时的位置记录下来，这是输出的根本。很多人在输入完时间之后忘了存编号，排序完再想找原编号就来不及了。
排序循环里的sum += prefix;对应的是“当前这个人干等了多久”。由于第1个人等待时间为0，所以第一轮加进去的也是0，不会影响结果；但代码逻辑上是从第1个人开始统一处理的，这是刻意保留这种写法的，因为它和“等待时间不含自己接水”的定义完全对应。
最后一行输出平均时间，(double)sum / n先转类型再除，保证浮点精度。
3.2 Python 完整实现
Python的代码思路一样，但有几个地方写起来更顺手或者更需要注意。
n = int(input()) a = list(map(int, input().split())) arr = [(t, i + 1) for i, t in enumerate(a)] arr.sort() prefix = 0 total = 0 order = [] for t, idx in arr: total += prefix prefix += t order.append(str(idx)) print(" ".join(order)) print(f"{total / n:.2f}")Python的元组排序天然就是“先按时间，时间相同按下标”，省去了写比较函数的麻烦。这题的n很小，直接用列表就行，不需要优化。
print(" ".join(order))这里我先把编号转成字符串再拼接，如果用print(order)会输出带方括号和逗号的列表，格式不对。输出格式是算法题里非常容易丢分的地方，建议每道题都习惯性按样例比对一遍格式。
3.3 复杂度和数据范围分析
排序是O(n log n)，累加是O(n)，所以整道题的时间复杂度就是O(n log n)。空间复杂度O(n)，因为要保存每个人的时间和编号。
n的范围通常是1000以内，所以无论如何都不会超时。但n小不代表可以随便用O(n^2)的写法，比如每次选出当前最小时再来一个双重循环，虽然也能过，但违背了这道题训练贪心和排序的初衷。做题的意义不是AC就行，而是通过一道题掌握一类解决思路。排序完后一趟累加，这种O(n log n)的做法才是这个题最值得学到的东西。
数据范围这里，虽然n不大，但建议所有累加变量都用long long。原因在第四章详细说，这里是提前打个疫苗。
4. 踩坑记录与排查思路
4.1 时间累加越界：int 不够用
有朋友会问，n最大也就1000，接水时间再大能有多大？但如果每个Ti可以到1e6，最坏情况下总等待时间可以到n^2 * Ti这个量级，1000 * 1000 * 1e6就是1e12级别，远超int的21亿上限。
用long long是不会错的选择。就算你现在拿到的数据范围小，养成累加用64位整数的习惯，对后面做更大数据范围的题很有帮助。这个习惯就是算法竞赛里常说的“取值范围先行”。
4.2 把平均等待时间算成0.00
这是最常见WA点之一。如果写的是printf("%.2f\n", sum / n);而sum和n都是整数，结果会先做整数除法，小数部分被截断，再转成浮点数输出。比如10/4会先算成2，再输出2.00，而不是2.50。
排查思路很简单：看到输出全是.00结尾，第一反应就是检查除法两边类型。强制转换其中一个操作数为double，问题立刻解决。
4.3 排序后输出编号顺序搞反
题目要输出的排序顺序是：第一个位置放谁，第二个位置放谁，依次输出编号。不要把它理解成“按编号从小到大输出时间”。有人排完序之后把p[i].id当成时间输出了，这也是典型错误。
调试时可以拿样例跑：输入1 2 3 4，排序后arr是(1,1),(2,2),(3,3),(4,4)，输出1 2 3 4，看不出问题；但如果你换个乱序输入，比如3 1 2，正确输出应该是2 3 1，按时间升序对应原始编号是2(时间1)、3(时间2)、1(时间3)。用乱序数据自测一遍，就能看出排序和编号输出是否对应。
4.4 平均等待时间公式的另一种推导
这题还有一个公式可以快速算总等待时间：把排好序后的时间，从第1个到第n-1个，分别乘以(n-1)、(n-2)、...、1，全部加起来。也就是sum += t[i] * (n - i);。
我们可以验证一下样例：t = [1,2,3,4]，n=4，sum = 13 + 22 + 3*1 = 10，平均2.50。
这个公式在推导上很直观：第1个人接水时，后面3个人都在等，所以他的1分钟贡献了3分钟等待；第2个人接水时，后面2个人在等，贡献22=4分钟；第3个人贡献31=3分钟。第4个人接水时没有人等他，所以不计。
两种公式选哪种看个人习惯，但用加权公式时尤其要注意循环下标别从0开始搞混。如果数组从0开始存，写成sum += t[i] * (n - i - 1)才对。
5. 从一道题到一类问题：贪心还能用在哪
5.1 操作系统里的“短进程优先”调度
P1223 排队接水本质上就是调度问题。操作系统里有一个经典的CPU调度算法叫SJF（Shortest Job First，短作业优先），思路就是让执行时间最短的进程先运行，从而降低所有进程的平均等待时间。
两边的模型几乎一模一样：一个CPU（一个水龙头），一批到达时间相同或者可以排队等待的任务（接水的人），每个任务有已知执行时间（接水耗时）。目标是最小化平均等待时间。所以做完P1223，你其实已经把操作系统的SJF调度思想过了一遍。
现实中的操作系统很少直接使用纯SJF，因为实际环境中无法准确预知每个进程的运行时间，而且短进程一直被插队会导致长进程饿死。但理解SJF是理解更复杂调度算法（比如最短剩余时间优先、多级反馈队列）的基础。算法题和生活经验之间的桥梁，就是这么搭起来的。
5.2 多水龙头版本：排队打水问题的进阶
如果题目把条件改成“有m个水龙头可以同时接水”，那情况就复杂一些了。此时不能简单升序一个个排，而是要尽量把耗时长的任务分散到不同水龙头，避免某一列队伍特别长。
常见的策略是：先把所有人按接水时间排序，然后用一个小根堆维护每个水龙头当前累计的占用时间，每次把下一个任务分配给当前累计时间最少的水龙头。这个过程每步都选择“当前最闲的水龙头”，本身又是一个贪心选择，配合优先队列实现，复杂度O(n log m)。
这种变化版在面试里也很常见，其实就是在P1223的基础上多问一句：“如果资源可以并行呢？”从单机调度到多机并行，贪心策略从简单排序升级为“排序+优先队列”，解题路径的延伸非常自然。
5.3 加权等待时间：当每个人的时间价值不同
现实里不是所有人“每分钟”都等价。医院急诊分诊就是例子：危重病人需要优先处理，而不是只看“处理时间短”。如果给每个人加上一个权重w_i，表示每等待一分钟产生的代价，目标变成最小化加权总等待时间，贪心策略就变了。
这时正确的排序依据是“接水时间/权重”的比值，比值小的排前面。这就是调度理论里的Smith规则。核心思想从P1223的“短作业优先”扩展成“单位权重占用时间越少越优先”。如果你在面试中遇到这种变形，能联想到P1223的证明框架，很快就能推出正确排序规则。
6. 实操心得与扩展建议
最后分享两个我实际刷题过程中总结出来的小技巧，对做P1223和后面的贪心题都有帮助。
第一个技巧是先写暴力再写贪心。如果刚开始对贪心正确性不放心，可以先写一个全排列枚举所有顺序的暴力程序，n很小的时候是能出结果的；再把贪心程序的输出和暴力结果对比，跑几组随机数据就能验证自己的贪心策略。这个习惯在遇到思路不确定的题目时特别有用。暴力代码可能超时，但它的作用是当参照物，不用于提交，只用于对拍。
第二个技巧是格式化输出前先跑一遍样例。我这道题第一次提交就是挂在输出格式上，样例输入是1 2 3 4，顺序本来就升序，看不出编号和时间的对应关系，最后输出好了但多输出了一个空格，被判PE（格式错误）。后来我习惯用乱序数据自测，比如输入3 1 2，如果输出不是2 3 1，就说明排序和编号之间有bug。这个自测习惯帮我避开了很多次不必要的罚时。
P1223排队接水虽然简单，但它是理解贪心算法、排序应用、格式输出的一个综合入门点。做完这道题，你对“为什么排序能优化等待时间”“为什么要保存原始索引”“为什么累加要用long long”这三个问题就有了具体答案。带着这套经验去刷后续的贪心题单，你会发现自己看题的速度明显不一样。
