企业官网建设流程全解析

信息学奥赛一本通 1319 和洛谷 P1223 其实指的是同一道经典贪心题：排队接水。很多初学者看到“排队”两个字，第一反应就是去模拟队列、维护时间轴，结果越写越复杂；真正做对的人，往往两三行排序就结束了。我第一次做这题时也被“平均等待时间最小”绕了一下，后来才发现核心就一句话：接水时间短的人先接，总等待时间就最小。这篇文章会把题目背后的贪心证明、代码实现、常见踩坑全部拆开讲清楚，适合刚学贪心或者准备信息学奥赛的选手参考，照着写就能在洛谷 P1223 上一遍过。

1. 题目到底在问什么：排队接水的核心矛盾

1.1 一句话说清题意

有 n 个人在同一个水龙头前排队接水，每个人都有自己的接水时间 Ti。题目要求你给出 1 到 n 的一个排列，也就是让谁排第几个，使得这 n 个人的“平均等待时间”最小。

这里的关键词是“等待时间”。按信息学奥赛一本通和洛谷 P1223 的定义，等待时间一般指这个人从开始排队到轮到他接水之前所花的时间，不包括他自己接水的时间。也就是说，第一个人等待时间是 0，第二个人等待时间是第一个人的接水时间，第三个人等待时间是前两个人接水时间的和，依此类推。

输入格式很固定，第一行一个人数 n，第二行 n 个数分别代表第 1 个人到第 n 个人的接水时间。输出也分两行：第一行是最优排队顺序，也就是人员编号的排列；第二行是这个顺序下的平均等待时间，保留两位小数。

很多人会在第二行栽跟头，因为题目要的是“平均等待时间”，不是“总等待时间”，更不是“所有人完成接水的总时间”。这三者只差一个除以 n，但如果题意理解偏了，样例输出怎么都对不上。

1.2 手算一个完整样例

洛谷 P1223 的样例输入长这样：

10 56 12 1 99 1000 234 33 55 99 812

一共有 10 个人，每个人的接水时间分别是：

• 第 1 人：56
• 第 2 人：12
• 第 3 人：1
• 第 4 人：99
• 第 5 人：1000
• 第 6 人：234
• 第 7 人：33
• 第 8 人：55
• 第 9 人：99
• 第 10 人：812

按“接水时间短的人先接”来排，顺序应该是第 3 人、第 2 人、第 7 人、第 8 人、第 1 人、第 4 人、第 9 人、第 6 人、第 10 人、第 5 人。也就是：

3 2 7 8 1 4 9 6 10 5

对应的接水时间序列是：

1 12 33 55 56 99 99 234 812 1000

我们来手算每个人的等待时间：

• 第 1 个排队的第 3 人：等待 0
• 第 2 个排队的第 2 人：等待 1
• 第 3 个排队的第 7 人：等待 1 + 12 = 13
• 第 4 个排队的第 8 人：等待 13 + 33 = 46
• 第 5 个排队的第 1 人：等待 46 + 55 = 101
• 第 6 个排队的第 4 人：等待 101 + 56 = 157
• 第 7 个排队的第 9 人：等待 157 + 99 = 256
• 第 8 个排队的第 6 人：等待 256 + 99 = 355
• 第 9 个排队的第 10 人：等待 355 + 234 = 589
• 第 10 个排队的第 5 人：等待 589 + 812 = 1401

所有等待时间加起来是：

0 + 1 + 13 + 46 + 101 + 157 + 256 + 355 + 589 + 1401 = 2919

平均等待时间就是：

2919 / 10 = 291.90

所以输出样例第二行是291.90。这个手算过程最好自己完整推一遍，因为很多排序题不是不会排序，而是不知道排序后该怎么累加。

2. 贪心思路：为什么耗时短的人先接水

2.1 先用“等待转移”的方式看总等待

要理解贪心策略，先把总等待时间换一种写法。

假设最优排队顺序是 p1, p2, ..., pn，那么第 pi 个人接水的时间会被后面所有 n - i 个人分别等待一次。换句话说，总等待时间可以写成：

总等待时间 = T[p1] * (n - 1) + T[p2] * (n - 2) + ... + T[pn-1] * 1 + T[pn] * 0

这其实就是把每一段接水时间对总等待的“贡献”单独拎出来。比如第一个人接水用了 T[p1] 分钟，排在他后面的 n - 1 个人每个人都要多等 T[p1] 分钟，所以这一项对整个总等待时间的贡献是 T[p1] * (n - 1)。

这个公式很有用，它能解释为什么短任务必须靠前：一个接水时间很长的人放在前面，会导致后面所有人一起陪他等，代价被放大了好几倍；接水时间短的人放在前面，即使他不幸排在很前面，代价也很小。

如果用代码实现，最常见的写法不是每次乘人数，而是维护一个前缀和。从前往后扫，每个人等待的时间就是当前已经累计的接水时间之和，扫完再把这个人自己的接水时间加进去。两种方式结果完全一样，前缀和写法更不容易出现下标错误。

2.2 交换相邻两人，证明排序的正确性

光靠直觉不够，信息学竞赛里最好掌握一个能写出来的证明方法：交换论证。

假设当前序列里有相邻的两个人 X 和 Y，X 排前面，Y 排后面，并且 X 的接水时间 a 大于 Y 的接水时间 b。我们来看看交换 X 和 Y 之后，总等待时间会怎么变。

这两个人之外的其他人，等待时间不受交换影响。因为 X 和 Y 作为整体，占用的时间段长度仍然是 a + b，排在他们前面的人不受影响，排在他们后面的人等待的累计起始时间也不变。所以只需要看 X 和 Y 这两项对总等待时间的贡献。

交换前：

• X 在位置 k，贡献是 a * (n - k)
• Y 在位置 k+1，贡献是 b * (n - k - 1)

交换后：

• Y 在位置 k，贡献是 b * (n - k)
• X 在位置 k+1，贡献是 a * (n - k - 1)

比较交换前后的大小，用交换前的贡献减去交换后的贡献：

[a * (n - k) + b * (n - k - 1)] - [b * (n - k) + a * (n - k - 1)] = (a - b) * (n - k) - (a - b) * (n - k - 1) = a - b

因为 a > b，所以这个差值大于 0。也就是说，交换前总等待时间比交换后更大，把耗时长的 X 和耗时短的 Y 交换之后，总等待时间一定会变小。

那就意味着，只要序列中还存在着“耗时长的排在耗时短的前面”这样一对相邻元素，就一定能通过交换让总等待时间更小。一直交换下去，最终序列必然是按接水时间从小到大排列。这个过程和冒泡排序很像，所以贪心策略的正确性就被严格证明了。

2.3 平均与总和的关系

题目求的是“平均等待时间最小”，而平均等待时间等于总等待时间除以 n。在 n 固定的情况下，总等待时间最小，平均等待时间自然最小。所以解题时可以放心大胆地把目标定为最小化总等待时间。

这个“除以 n”的小细节，在证明里也经常被忽略。有些人写题解时会说“总等待时间最小等价于平均等待时间最小”，这句话成立的前提就是人数 n 不变。本题人数是输入固定的，所以没有任何问题。

3. 代码怎么写：C++ 和 Python 的完整实现

3.1 C++ 排序 + 前缀累计

我用的是结构体数组，里面存两个东西：接水时间 t 和原始编号 id。排序时按 t 从小到大；如果 t 相同，按 id 从小到大，这样输出顺序更稳定，也不会影响答案正确性。

#include <bits/stdc++.h> using namespace std; struct Person { long long t; int id; }; bool cmp(const Person& x, const Person& y) { if (x.t != y.t) return x.t < y.t; return x.id < y.id; } int main() { int n; cin >> n; vector<Person> a(n); for (int i = 0; i < n; ++i) { cin >> a[i].t; a[i].id = i + 1; } sort(a.begin(), a.end(), cmp); long long totalWait = 0; long long prefix = 0; for (int i = 0; i < n; ++i) { if (i) cout << ' '; cout << a[i].id; totalWait += prefix; prefix += a[i].t; } cout << '\n'; printf("%.2lf\n", (double)totalWait / n); return 0; }

这里几个点要特别注意。

前缀 prefix 表示当前这个人之前所有人的接水时间之和，所以先累加到 totalWait，再把自己时间加进 prefix。这样第一个人的等待时间就是 0，最后一个的等待时间也能正确算出来。

totalWait 一定要用 long long。虽然洛谷 P1223 的 n 不算很大，但 Ti 可能上千，乘上后面排队人数之后，容易超过 int 的范围。比赛里图省事用 int 爆掉，是很不划算的。

输出平均等待时间时，(double)totalWait / n要写成这样，不能写成(double)(totalWait / n)。后者会先把整数除完再转 double，小数部分直接丢掉了。

如果想用公式写，也可以不在循环里维护前缀，直接对排序后的数组再扫一遍：

long long totalWait = 0; for (int i = 0; i < n; ++i) { totalWait += a[i].t * (n - i - 1); }

这个写法对应的是“排在第 i 位的人会被后面 n - i - 1 个人等”。两种写法等价，选自己喜欢的一种就行。

3.2 Python 版本

Python 的写法更简洁，核心就是 sort 的 key。

n = int(input()) times = list(map(int, input().split())) people = [(times[i], i + 1) for i in range(n)] people.sort(key=lambda x: (x[0], x[1])) order = " ".join(str(idx) for _, idx in people) prefix = 0 total_wait = 0 for t, _ in people: total_wait += prefix prefix += t print(order) print(f"{total_wait / n:.2f}")

Python 的整数不会溢出，long long 的问题自动不存在。但要注意input().split()可能因为输入行有多个空格而得到空串，实际 OJ 输入一般不会出现这种情况，所以直接用没问题。

输出保留两位小数，建议用 f-string 的:.2f，不要用round，因为 round 有时候不会补全末尾的 0。比如291.9和291.90，题目要求的是后者。

3.3 两种计算总等待的公式

我整理了一个小表，方便对照：

用前缀和法，公式是每到一个位置，把 prefix 加进答案，再加当前人的时间；用乘法贡献法，公式是每个位置都用当前时间乘以后面人数。这两种方法我在代码里都试过，前缀和更贴近“等待时间”的定义，乘法贡献法更贴近贪心证明，想明白其中一种，另一种自然就通了。

4. 实战中的坑：洛谷和一本通提交经验

4.1 先查这 5 个地方

我在给学员看代码时，发现提交不通过的原因往往很集中。遇到 WA 或者样例过不去，先检查以下 5 个点：

1. 排序时是不是把时间排对了，而不是按编号排。
2. 输出第一行时，输出的是原始编号 id，不是接水时间 t。
3. 第二行输出的是平均等待时间，不是总等待时间。
4. 平均等待时间保留两位小数，格式不能错。
5. 所有涉及累加的变量，是否用了 long long。

这 5 个点里，第 2 个最容易犯。很多新手排序后一高兴，直接输出排序后的时间数组，样例输入如果恰好是 1 到 n 的某种排列，可能还看不出来；一旦数据变成正常的大整数，立刻全错。

4.2 等待时间定义最容易搞混

我见过不少题解在计算时用totalWait += a[i].t * (n - i)，而另一些题解用totalWait += a[i].t * (n - i - 1)。两个写法如果下标基准不一样，其实都是对的。关键是先搞清楚自己的 i 是从 0 开始还是从 1 开始。

如果 i 从 0 开始，排序后数组下标是 0, 1, ..., n-1，那么第 i 个人后面有 n - i - 1 个人，所以贡献是a[i].t * (n - i - 1)。

如果 i 从 1 开始，第 i 个人后面有 n - i 个人，所以贡献是a[i].t * (n - i)。

最怕的是混着用。比如用 0 下标却写成 n - i，最后答案会多算一遍，而且很难肉眼发现。建议统一用前缀和法，彻底绕开下标问题。

还有一种错误是，把“等待时间”理解成“从开始排队到接完水的时间”。如果这样理解，总等待时间会变成所有人完成时间的和，和题目要求完全不一样。做题前先确认输出样例，如果样例能给到291.90，那说明是标准的“不含自己的等待时间”。

4.3 样例过了还是 WA？逐项排查

如果你已经能够正确输出样例，但提交后还是 WA，大概率是细节问题。

先看输出空格的格式。我用的是循环里判断if (i) cout << ' ';这种方式，可以避免行末多一个空格。有些 OJ 对行末空格不敏感，但有些会对；写规范一点总没错。

再看第二行的换行。洛谷一般接受行末换行，但第一行和第二行之间一定要有换行。最后一行结束有没有换行通常无所谓，可如果使用printf输出，建议末尾带\n。

再看 sort 比较器。如果自己写的 cmp 里只写return x.t < y.t;，在时间相同时，两个元素会被视为“都不小于对方”，这本身符合严格弱序，程序不会崩。但有些平台为了稳定性，期望相同时间的元素维持输入顺序，这时可以在 cmp 里加上if (x.t == y.t) return x.id < y.id;。加了之后输出更好看，也不影响正确性。

如果编译错误，先查bits/stdc++.h是否被 OJ 支持。洛谷的 C++ 环境通常支持，但个别 OJ 可能不支持，那就换成#include <iostream>、#include <algorithm>、#include <vector>和#include <cstdio>。

5. 从排队接水延伸出去

5.1 多水龙头排队

如果题目改一下，变成 r 个水龙头同时工作，所有人在 r 个队伍前排队，策略就不再是简单的全局排序了。这时候要用“贪心 + 小根堆”或者“排序后均匀分配”的思路，核心是让当前最早空闲的水龙头去接下一个耗时最短的人。

虽然代码复杂一些，但底层逻辑仍然是“短任务优先”。因为短任务先被处理掉，后续队伍的长度和等待时间才不会积累。信息学奥赛一本通后面有很多这类变体题，都是从排队接水延伸出来的。

5.2 同类贪心题的共同套路

排队接水属于非常典型的“排序类贪心”。这种题有一个共同的套路：先想一想，如果任意两个相邻任务交换顺序，会对最终答案产生什么影响。只要列出影响表达式，证明出“某种顺序严格优于另一种”，贪心策略就出来了。

活动安排、最小化迟到惩罚、哈夫曼编码，本质上都在反复用同一个思想。所以我不建议只看题解背结论，而是建议动手把交换论证写一遍。写熟之后，看到一个新贪心题就不会慌，因为你知道自己有能力验证它。

5.3 一个可以记下来的公式

对于单水龙头排队接水，排序后总等待时间的公式是：

总等待时间 = T1 * (n - 1) + T2 * (n - 2) + ... + Tn-1 * 1

这里 T1 是排序后第一个人的接水时间，Tn 是最后一个，最后一项是 0 所以不写。平均等待时间就是这个值除以 n。

做题时我习惯先写出这个公式，再倒推贪心策略。公式里 T1 的系数最大，所以 T1 必须最小；T2 的系数第二大，所以 T2 必须第二小。系数越大，越要把小时间放上去，这就是“短任务优先”最直观的解释。

我个人在实际做题中的体会是：排队接水这道题不难，但特别适合用来检验自己对贪心的理解是不是只停留在“感觉对”。如果把交换证明、两种计算总等待的方法、输出格式都吃透了，那么洛谷 P1223 基本就是一道送分题。之后遇到任何“平均等待”“总等待”“排队耗时”有关的题目，都能很快反应过来该不该排序、该用哪种顺序。最后再分享一个小技巧：写完代码后，自己多构造一组“每个人时间都相等”的数据试一下，这时候无论怎么排队答案都一样；如果程序输出发生了变化，那就要检查排序稳定性或者计算逻辑了。