最近在洛谷刷题的时候又碰上了 P1223 排队接水说实话这题本身不难但评论区里每天都有人在问“为什么我的答案不对”“为什么总等待时间算出来是负数”“为什么输出顺序和样例不一样”。作为一个把贪心、排序、前缀和、浮点格式化输出这些基础点串在一起的经典题它非常适合用来检验自己对基础功的掌握程度。这篇文章我就从题意拆解、贪心证明、三种代码写法到实际提交时的坑完整过一遍希望能帮到正在刷这题的人也让准备机试或面试的读者顺手把这类“排队最小化等待时间”模型吃透。1. 题目到底在说什么P1223 排队接水的完整题意1.1 大白话版题面题目讲的是有 n 个人在一个水龙头前面排队接水。每个人接水需要的时间不一样比如第 1 个人可能要 3 分钟第 2 个人可能只要 1 分钟。排队的时候每个人都要等前面所有人接完水才轮到自己接。要求你重新安排这 n 个人的顺序让所有人等待时间的平均值最小。这里要特别注意的是“等待时间”的定义。如果你排在第一个你的等待时间是 0如果你排在第二个你的等待时间就是第一个人的接水时间如果你排在第三个你的等待时间等于前两个人的接水时间之和依此类推。所以总等待时间就是每个人等待时间的总和最后再除以 n得到平均等待时间。题目输入第一行给 n第二行给 n 个正整数表示每个人接水需要的时间。输出要分两行第一行输出一种排队顺序注意不是时间而是原始编号的顺序第二行输出该方案下的平均等待时间保留两位小数。1.2 核心考点清单这题能出现在很多算法入门必刷清单里是因为它表面是一道“贪心”题实际上把好几个基础知识点串在一起了。第一个考点是贪心策略。你要能判断出“接水时间短的人排在前面”能让总等待时间最小。这个结论很多同学凭直觉就能猜到但题目要的不只是猜还要能证明和理解为什么交换相邻两人就能推翻非最优解。第二个考点是带序号的排序。输入给的是每个人接水时间但输出要求的是编号顺序所以排序时不能把编号丢了。这是个很常见的套路结构体、类、元组把值和原始下标绑在一起排序。第三个考点是总等待时间的计算。最容易出错的地方在于累加逻辑。如果理解成“让人在排队时把前面接水时间都加起来”就需要一个循环累加如果掌握了公式直接用 t[i] 乘以剩余人数也能算。两种方式求出来结果一样但有意训练对一个模型的多角度理解是个好习惯。第四个考点是浮点输出精度。平均等待时间要保留小数点后两位C 里用 printf(%.2f)Java 里用 System.out.printf(%.2f)Python 里用 f{avg:.2f}。看起来都是小细节但格式化出问题照样 WA。1.3 数据范围与复杂度预期洛谷原题 P1223 的 n 范围我记得在千级别人数不多但接水时间本身是整数累加以后总等待时间的数量级会比较大这一点非常关键。很多人第一次写这题用 int 存总和结果溢出了还不知道错在哪。就算 n 只有 1000如果每个人的接水时间都接近 1e6那么总等待时间大约是 1e6 * 1000 * 1000 / 2也就是 5e11 这个量级int 撑死大约 2.1e9肯定装不下。所以累加总等待时间的变量必须要用 long long 或者等价的 64 位整数类型。时间复杂度上排序是 O(n log n)遍历计算是 O(n)空间复杂度 O(n)。哪怕数据范围再放大到 1e5这个解法也完全没有压力。所以一看到这种“重新排序 求最优目标”的题优先往排序方向上想通常没错。2. 为什么“接水快的排前面”就是最优解2.1 先给结论再给证明结论很简洁把所有人按接水时间从小到大排序就是最优排队顺序。这也符合生活中的直觉去超市结账的时候如果前面是个只买一瓶水的人你肯定希望他先结而不是让推着一整车商品的人慢慢来。但作为算法题光靠直觉不够还要有严谨的证明。这里分享一个非常经典的“相邻交换法”证明理解以后能用在大量贪心排序题上。假设当前有一种排队方案其中存在相邻的两个人 i 和 j且 i 排在 j 前面但 ti tj也就是说接水慢的人排在接水快的人前面。我们看交换 i 和 j 会对总等待时间产生什么影响。交换 i 和 j 之前排在 i 前面的人的等待时间不受影响排在 j 后面的人等待时间也不受影响。受影响的只有 i 和 j 两个人。假设 i 前面所有人接水时间总和为 S那么在交换前i 的等待时间是 Sj 的等待时间是 S ti所以 i 和 j 两个人等待时间合计是 2S ti。交换 i 和 j 之后j 在 i 前面j 的等待时间是 Si 的等待时间是 S tj合计变成 2S tj。因为 tj ti所以 2S tj 2S ti。这说明交换之后总等待时间变小了。只要存在一个相邻逆序对总等待时间就不是最优。反复进行这类交换最终所有逆序对都会消失也就是形成一个按接水时间从小到大排列的顺序。所以说递增排序就是唯一能让人均等待时间最小的方案。2.2 平均等待时间的两种计算公式排序完成后我们要计算总等待时间。设排序后的数组为 a[0], a[1], ..., a[n-1]其中 a[0] 是接水时间最短的人。按照定义第一个人等待时间 0第二个人等待时间 a[0]第三个人等待时间 a[0] a[1]一直加到最后一个人。最直接的模拟写法就是用一个 cur 变量记录当前人已经等待了多长时间每次轮到下一个人时把上一个人的接水时间累加进去再加入总和中。另一种更快的计算方式是用公式。观察每个 a[i] 会被多少个人等待可以这样想a[0] 排第一个后面 n-1 个人等待它所以 a[0] 出现 n-1 次a[1] 排第二个后面 n-2 个人等待它所以 a[1] 出现 n-2 次。最后一个人自己不需要等待自己所以 a[n-1] 出现 0 次。总等待时间 sum(a[i] * (n - i - 1))。这两种写法我都推荐大家亲手实现一遍。模拟写法的好处是思路直接不容易算错公式写法的好处是代码精简而且真正理解了这个式子以后再看类似“每个人被后面多少人等”的题会很快反应过来。2.3 这个模型还能用在哪排队接水模型并不是只存在于竞赛题里它背后是计算机系统和生产生活里非常常见的短作业优先调度思想。比如操作系统里的进程调度。多个任务提交到 CPU每个任务需要的执行时间不同想让所有任务从提交到运行完成的平均周转时间最短一般就会优先执行执行时间短的任务。这和排队接水的目标完全一致。再比如磁盘 IO 调度里多个请求排队等待磁盘服务如果服务时间差异明显优先服务耗时短的请求也能降低平均等待时长。仓储拣货、维修派单、客服分配多少都能套上这个模型。所以别看 P1223 只是个小题目它传达的“短作业优先”思想在很多工程场景里都能用上。理解了这一点刷题就不只是刷题而是积累了一类可迁移的优化思路。3. 三种语言实现C、Java、Python 任你选3.1 C 版本结构体排序C 是我最推荐的入门实现语言之一因为结构体加 sort 的写法非常直观而且能顺便把 C 的排序比较器也练了。#include bits/stdc.h using namespace std; struct Node { int t; // 接水时间 int id; // 原始编号 }; int main() { int n; cin n; vectorNode a(n); for (int i 0; i n; i) { cin a[i].t; a[i].id i 1; } // 时间从小到大排序时间相同时按编号从小到大排序 sort(a.begin(), a.end(), [](const Node x, const Node y) { if (x.t ! y.t) return x.t y.t; return x.id y.id; }); long long sum 0; for (int i 0; i n; i) { cout a[i].id ; // 当前人的等待时间等于前面所有人的接水时间之和 // 等价写法sum 1LL * a[i].t * (n - i - 1) sum 1LL * a[i].t * (n - i - 1); } cout endl; printf(%.2f\n, (double)sum / n); return 0; }这里有几个细节值得说。排序用 Lambda 表达式比较逻辑是“时间不同比时间时间相同比编号”。这样不仅能保证标准顺序也能避免 C 里 sort 不稳定导致相同时间的人顺序被打乱。计算总等待时间时这里用的是公式直接把 a[i].t 乘以后面剩余人数然后累加。这里我特意加了1LL *目的是把乘法结果转成 long long防止 int 乘 int 先溢出再转类型。最后用 printf 保留两位小数。sum是 long long先除以 n 会得到整数部分丢失精度所以要先把 sum 转成 double再除 n。3.2 Java 版本Comparator 写法Java 的写法思路和 C 几乎一致只是语法上略有区别。我一般会用内部类或者数组来保存编号和时间排序时通过 Comparator 指定比较规则。import java.util.*; public class Main { static class Node { int t, id; Node(int t, int id) { this.t t; this.id id; } } public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); Node[] a new Node[n]; for (int i 0; i n; i) { int t sc.nextInt(); a[i] new Node(t, i 1); } Arrays.sort(a, (x, y) - { if (x.t ! y.t) return x.t - y.t; return x.id - y.id; }); long sum 0; for (int i 0; i n; i) { System.out.print(a[i].id ); sum (long) a[i].t * (n - i - 1); } System.out.println(); System.out.printf(%.2f\n, (double) sum / n); } }Java 里 Arrays.sort 对于对象数组的排序使用的是归并排序或 TimSort是稳定排序。但即便稳定我仍然建议在 Comparator 里把 id 作为第二关键字写明白这样代码语义更明确也避免后续调整数据时出现问题。有一点要提醒Java 中(x, y) - x.t - y.t的写法在数据值比较小的时候没问题但如果 t 是很大的 int差值可能溢出导致排序错误。这道题一般不会触发但养成用Integer.compare(x.t, y.t)的习惯会稳妥得多。3.3 Python 版本最简洁的排序Python 写这个题非常舒服因为元组排序天然支持按多个关键字排序。n int(input()) times list(map(int, input().split())) # 把时间和编号打包成元组按时间排序时间相同按编号排序 a sorted([(times[i], i 1) for i in range(n)]) # 输出编号顺序 order [str(id) for _, id in a] print( .join(order)) # 计算总等待时间 total 0 for i, (t, _) in enumerate(a): total t * (n - i - 1) print(f{total / n:.2f})sorted天然稳定所以如果出现相同时间谁先出现在列表里谁就排在前面。这里我在列表生成时直接按原始顺序打包所以相同时间会保持输入顺序恰好符合输出要求。总等待时间的计算方式和 C 的公式版本一样。Python 的 int 是任意精度所以即使数据大了也不会溢出这是 Python 刷题相对省心的一个点。3.4 排序时如何保住原编号很多第一次做这道题的人会犯一个经典错误直接对时间数组排序然后输出下标i1。比如时间数组是[5, 3, 3]排序变成[3, 3, 5]然后输出了1 2 3但实际正确顺序应该是2 3 1或3 2 1这种。原因很简单你排序的是值和编号的绑定关系丢了。正确做法是把原始编号和接水时间作为一个整体记录排序时携带编号一起移动。这也是一种非常重要的编程习惯后面做“物品按价值排序但要输出名称”“学生按成绩排序后输出学号”等需求时都会用到。4. 提交前必看这些细节决定你是 AC 还是 WA4.1 总等待时间计算为什么必须开 long long这是这道题最高频的 WA 原因之一。前面算过即使 n 只有 1000每个接水时间范围稍大总等待时间就能轻松超过 int 的 2.1e9。更别提有些训练平台会把数据放宽到 1e5那总等待时间的量级会直接来到 1e11 甚至更大。在 C 和 Java 中我建议把总等待时间变量直接用 long long 声明。C 计算乘法时要确保至少有一个操作数是 long long避免 int 乘法溢出的问题。写法上可以是sum 1LL * a[i].t * (n - i - 1)也可以先转成 long long 再乘。还有一个容易忽略的小坑printf 输出浮点数时虽然参数是 double但如果你在 sum / n 这里写的是整数除法结果会先变成整数再转 double导致小数部分丢失。所以一定要写成(double)sum / n。4.2 平均等待时间保留两位小数的正确姿势保留两位小数在三种语言里写法不同但我见过不少人在 C 里用了cout fixed setprecision(2) avg却忘记 includeiomanip或者在 Java 里用 DecimalFormat 但是舍入模式设置不对导致四舍五入结果有偏差。最稳妥的其实是直接使用 printf / format 家族的格式化输出它们默认会做四舍五入而且行为在各平台上比较统一。C 用printf(%.2f\n, (double)sum / n)Java 用System.out.printf(%.2f\n, (double) sum / n)Python 用 f-string 或者print({:.2f}.format(total / n))。注意 Python 的 f-string 格式化浮点数时会遵循四舍六入五成双的规则但竞赛平台通常不纠结这种边界所以直接用即可。4.3 重复接水时间的顺序问题当两个人接水时间相同时比如 t1 2 和 t2 2谁排在前面并不会影响平均等待时间因此从数学角度看两种顺序都满足“最优”。但从代码输出来看如果题目对输出顺序有具体要求就必须处理这个并列情况。洛谷 P1223 对输出顺序的判定通常不会卡得太死只要平均等待时间正确任意一种最优排列都可能被接受。不过为了形成稳定的输出方案我建议统一在排序时把原始编号作为第二关键字。这样即使换一台机器、换一个语言输出结果也是确定的便于和样例或自己对拍。C 的 sort 不是稳定排序所以不写第二关键字的话相同时间的人顺序可能是乱序。Java 的对象排序虽稳定但写成 Comparator 后是否稳定由具体算法决定最好也别依赖。Python 的 sorted 是稳定的但为了跨语言统一也建议通过元组明确指定第二关键字。4.4 边界情况n 等于 1 时别翻车如果 n 1只有一个人排队接水他的等待时间是 0平均等待时间也是 0.00输出的排队顺序当然是编号 1。很多代码在 n 较小时不会出问题但如果你习惯用“第 i 人等待第 i-1 人接水”这种累加逻辑要确保循环边界写对不要访问负下标。另外输入格式也可能因为你没有处理换行而出问题。有些平台输入行尾有多余空格或者第二行数据跨多行放置建议用流式读取不要用split后只读第一行这种方式。5. 常见问题速查直接帮你定位 WA 原因我在做题过程中把自己的错误和群友常问的问题整理过一张表覆盖了 P1223 排队接水绝大多数 WA 场景。错误表现可能原因解决办法输出编号顺序正确但平均等待时间不对总等待时间累加逻辑出错比如把“等待时间”算成了“完成时间”画一个 3 人的小例子手算一遍对比模拟写法和公式写法平均等待时间小数部分全是 0用了整数除法 sum / n忘记转 double写成 (double)sum / n大数据时输出负数或异常大数用 int 存总等待时间导致溢出换 long long输出顺序和样例一致但被判错排序没考虑相同时间时的稳定顺序在排序比较器中加入 id 作为第二关键字忘记输出第二行换行部分评测系统对行末空白敏感用 println 或 cout endl读入第二行时没有处理完所有时间使用 nextLine 时混用了 nextInt 和 nextLine导致读到空行统一用 nextInt 或先处理后换行这些问题是真实高频的尤其数据类型和格式化输出只要中一个就可能卡上半小时。建议提交前先拿小样例手算验证再考虑是否 AC。最后分享一点个人习惯这个题我至少写过五遍每次写都有新的体会。第一遍用模拟累加求总等待时间第二遍用公式优化第三遍开始尝试在排序比较器里加上第二关键字之后再碰到类似“国王游戏”“凌乱的 yyy”这类需要靠相邻交换证明贪心策略的题就自然知道第一步该做什么了。我的建议是刷这题时不要只抄代码亲自推一遍相邻交换的证明再用三种语言各实现一次。等到你能不看题解自己写出结构体排序、公式计算总等待时间、保留两位小数输出时这类“排队问题”的基本功就算到位了。后面遇到多水龙头版本也不过是在排序基础上再套一个优先队列而已。
