前两天刷题群里有人发了条链接问P1223 排队接水有没有什么通俗易懂的讲法。我当时回了句这题你只要抓住一句话——让接水快的人先上所有排队的人的总等待时间就越少。就是这么个直觉但真正把它讲清楚、写对还得拆开揉碎了看。P1223 排队接水是很多人入门贪心算法的第一道题。题目描述很生活化n个人在一个水龙头前排队接水每个人接水耗费的时间已知要求你给出一个排队顺序让所有人的平均等待时间最短并输出这个排队顺序以及对应的平均等待时间。题面看着简单但里面藏着三个关键点一是“等待时间”的定义二是为什么贪心排序有效三是怎么在排序后还能正确输出每个人的原始编号。这篇文章从题意、证明、代码实现到易错点完整过一遍希望能让刚接触贪心算法的朋友少走点弯路。1. 先搞懂题在问什么题意拆解与贪心直觉1.1 “等待时间”到底算到哪一刻第一次做这题的人十有八九会栽在这个概念上。题目里的等待时间指的是每个人从排在队伍开始到轮到自己接水之前这段干等的时间不包括自己接水的时间。拿样例说明。n4四个人接水时间分别是1、2、3、4。如果按1、2、3、4的顺序排队第1个人等待0分钟接水1分钟第2个人等了1分钟接水2分钟第3个人等了123分钟接水3分钟第4个人等了1236分钟接水4分钟。所以总等待时间 0 1 3 6 10平均等待时间 10 / 4 2.50。这个2.50就是题目样例输出。如果你把“等待时间”理解成“从开始排队到接完水的总耗时”那算出来的平均时间是 (13610)/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里最简单的写法是用一个结构体或者直接用pairint, int。pair排序默认先比较第一个字段再比较第二个字段这种天然特性在这道题里特别合适pairint, 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]n4sum 13 22 3*1 10平均2.50。这个公式在推导上很直观第1个人接水时后面3个人都在等所以他的1分钟贡献了3分钟等待第2个人接水时后面2个人在等贡献224分钟第3个人贡献313分钟。第4个人接水时没有人等他所以不计。两种公式选哪种看个人习惯但用加权公式时尤其要注意循环下标别从0开始搞混。如果数组从0开始存写成sum t[i] * (n - i - 1)才对。5. 从一道题到一类问题贪心还能用在哪5.1 操作系统里的“短进程优先”调度P1223 排队接水本质上就是调度问题。操作系统里有一个经典的CPU调度算法叫SJFShortest 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”这三个问题就有了具体答案。带着这套经验去刷后续的贪心题单你会发现自己看题的速度明显不一样。
