企业官网建设流程全解析

1. 题面其实在问什么：从“排队”到“数学模型”的转换

这道题我第一次看的时候，差点被它朴实的题目描述骗了。题目说得很直白：有n个人在一个水龙头前排队接水，每个人接水需要一定时间Ti，要找出一种排队顺序，使得所有人等待时间的总和最小（洛谷版要求平均等待时间最小，一本通版还额外要求输出排队顺序）。

先说结论：这题的正解是贪心，按接水时间从小到大的顺序排队，就能让总等待时间最短。但问题是——为什么？很多新手能猜到这个结论，但说不清背后的数学原理，换一道类似的题又不会做了。所以我这篇不打算只给代码，重点是把“为什么从小到大排序就一定最优”这件事掰开揉碎讲清楚。

先看一个具体例子。假设有3个人，接水时间分别是3、1、2。如果按3、1、2的顺序排队，那么：

• 第1个人（耗时3）等待0分钟，因为他不需要等别人
• 第2个人（耗时1）等待3分钟，也就是前面的人接水的时间
• 第3个人（耗时2）等待3+1=4分钟

总等待时间 = 0 + 3 + 4 = 7，平均等待时间 = 7 / 3 ≈ 2.33。

如果换成1、2、3的顺序：

• 第1个人（耗时1）等待0分钟
• 第2个人（耗时2）等待1分钟
• 第3个人（耗时3）等待1+2=3分钟

总等待时间 = 0 + 1 + 3 = 4，平均等待时间 = 4 / 3 ≈ 1.33。

差距一下子就出来了。7对4，差了将近一倍。而这还只是3个人，如果人数变成1000，错误的排队策略造成的等待时间浪费完全不是一个量级。

为什么会有这种差距？关键在于公式结构。n个人排队接水，每个人都要等前面所有人接完水才能轮到自己，所以第i个人的等待时间等于前i-1个人的接水时间之和。总等待时间就是：

T = 0 + T1 + (T1+T2) + (T1+T2+T3) + ... + (T1+T2+...+T(n-1))

把这个式子展开：第一名的耗时T1被重复加了n-1次，第二名的耗时T2被重复加了n-2次……最后一个人的耗时T(n-1)只被加了1次，最后一个人的耗时Tn压根不影响等待时间（因为他后面没人了）。

这就变成了一个典型的“权重分配”问题：耗时越短的人，应该放越靠前的位置，这样它的耗时被重复加的次数越少。用生活化的类比来说：你去奶茶店排队，如果前面站着几个要点五杯八杯的大客户，你肯定急得跳脚；但如果是每个人只点一杯，队伍流动就快得多。让耗时短的人先走，等于让整个队伍的人均等待时间降下来，这是这道题最核心的直觉。

2. 反直觉的贪心结论：为什么最省事的策略反而是最优解

很多人在看到这类题时，第一反应是“用动态规划”或者“模拟所有排列，取最小值”，但细想就知道不现实：n个人排队，排列方式是n!种，n等于1000时这个数字大到天文级别，枚举到宇宙毁灭都算不完。所以必须找规律。

这里就涉及贪心算法的核心思想：不追求全局所有可能的方案，而是每一步都做一个在当前看来最好的局部选择，并期望局部最优能推导出全局最优。排队接水恰好满足这个特性，所以能用贪心。

但这道题最“反直觉”的地方在于：就算你知道该按耗时从小到大排，也很难说清楚“调换任意两个人的顺序，总等待时间会变大”这个逻辑。我举个例子说明：任意选两个人，A耗时a，B耗时b，假设a < b。如果A排在B前面，那么在A和B这个局部里，B的等待时间会多一个a；如果反过来，B排在A前面，A的等待时间会多一个b。换序之前，A和B两人对总等待时间的贡献是a + (a+b)；换序之后变成b + (b+a)。一比较：

原来：2a + b 换后：a + 2b

因为a < b，所以2a + b < a + 2b。换句话说，把耗时短的人放前面，这个局部贡献一定更小。这个局部结论对任意一对人都成立，所以全局按这个规则排序，得到的方案就是最优的。

这种“交换论证法”是贪心算法里非常经典的证明手段，以后你遇到类似“排序后贪心”的题（比如区间调度、最小化最大延迟等），大概率还能用上。我建议你在草稿纸上自己推一遍这个公式，别看它简单，亲手写一遍和看一遍的感觉完全不一样，尤其是“为什么两个耗时相等的人谁先谁后无所谓”这个结论，推一次就能彻底理解。

关于输出排队顺序，还有个容易忽略的细节：如果两个人耗时相同，题目要求输出时保持输入顺序吗？原题洛谷P1223其实不要求输出顺序，一本通1319明确要求“输出排队顺序”。按什么规则输出？最稳妥的做法是用稳定排序，也就是耗时相同的人，按照输入顺序输出。C++的sort不是稳定排序，但pair排序时如果你把原始编号作为第二关键字，也能保证按输入顺序输出。这点后面写代码时我会演示。

3. 交换论证法：把“直觉上对”变成“数学上对”

前面我提到了“交换论证法”，这是这道题真正的灵魂，也是把它从“背题”变成“懂题”的关键。我打算专门用一个章节把它彻底讲透，因为这个方法你以后会在无数贪心题里见到。

交换论证法的标准套路分四步：

1. 假设有一个最优解，它和“目标排序”（本题是按耗时升序）不完全一致
2. 在最优解中找到相邻的两个元素，它们违反了目标排序的规则（比如耗时长的在前，耗时短的在后）
3. 交换这两个元素，证明交换后总代价不会变大（严格说是不会变小，即总等待时间不会增加）
4. 既然交换后依然是最优解，那就反复交换，直到变成目标排序。这说明目标排序也是最优解

第3步的数学推导，我拆开写一下：

设相邻两人A耗时a，B耗时b，原本A在B前面，但a > b（违反升序）。除A、B外，其他所有人的等待时间在交换前后完全不变，因为A、B作为一个整体占据的位置没变，排在它俩前面的人不受影响，排在它俩后面的人等待的总时间依然等于“前面这些人的耗时之和”，也没变。

变的只有A和B这两个人：

• 交换前：A等到0，B等到a
• 交换后：B等到0，A等到b

局部贡献从a变成了b。因为b < a，所以交换后局部贡献更小，总等待时间要么不变（a=b时），要么变小（a>b时）。这就证明了：只要存在相邻的逆序对（耗时长的在短的前面），交换它俩就一定不会让答案变差，所以升序排列必然是最优解。

这个证明的巧妙之处在于，它不需要考虑全局所有排列，只需要反复处理局部相邻的两个元素。它像不像冒泡排序的逻辑？没错，本质上一个逆序对都不剩时，数组就自然有序了。这也是为什么很多人说贪心题“看着像排序，其实背后是证明”。

还有一种常见的证明方式是把总等待时间构造成加权和：设每个人的耗时是Ti，下标是它在队伍中的位置，那么总等待时间 = ΣTi × (n - i)，其中i从1到n。这个公式直接说明：位置越靠前，权重n - i越大，所以应该把更小的Ti放在权重更大的位置。这是一个非常简洁的重排不等式视角，和交换论证法殊途同归。我建议两个证明都学一下，前者训练逻辑，后者训练数学建模能力，都是竞赛里的基本功。

4. 代码实现：C++和Java各给一版，注意数据类型和精度

搞懂了贪心策略，代码本身并不复杂。但“不复杂”不等于“没坑”，尤其是数据类型的选取和平均值的精度处理，经常有人在这里翻车。我先把题目数据范围明确一下：一本通和洛谷P1223的n上限都是1000，每个人的接水时间Ti是正整数，范围以题面为准。但注意，1000个数的累加和最大可能超过int的表示范围，所以存储总等待时间必须用long long（C++）或long（Java）。

先看C++版本：

#include <bits/stdc++.h> using namespace std; struct Person { long long time; int id; }; bool cmp(const Person &a, const Person &b) { if (a.time != b.time) return a.time < b.time; return a.id < b.id; } int main() { int n; cin >> n; vector<Person> p(n); for (int i = 0; i < n; i++) { cin >> p[i].time; p[i].id = i + 1; // 输入顺序编号，从1开始比较方便 } sort(p.begin(), p.end(), cmp); long long total = 0; long long prefix = 0; for (int i = 0; i < n - 1; i++) { prefix += p[i].time; total += prefix; } cout << p[0].id; for (int i = 1; i < n; i++) { cout << " " << p[i].id; } cout << endl; double avg = (double)total / n; printf("%.2f\n", avg); return 0; }

这里我用了结构体Person，里面存了两个字段：接水时间和原始编号。排序时如果时间相同，按编号升序排，这样就天然满足“稳定输出”的要求。

注意total的计算方式：我维护了一个prefix变量，累加当前人前面所有人的耗时，然后加到total里。这样写比直接套公式更直观，也不容易把下标搞错。循环只到n-1，因为最后一个人不产生等待时间。

这里有一个很多人会踩的坑：有人会贪方便直接写total += p[i].time * (n - i - 1)，这样也没错，但要注意p[i].time * (n - i - 1)这个乘积用int存会溢出。虽然n只有1000，但如果Ti给到10^9级别，乘积就超过int上限了。我在代码里把所有累计量都声明成long long，就是为了防这个。

再看Java版本：

import java.util.*; public class Main { static class Person { long time; int id; Person(long time, int id) { this.time = time; this.id = id; } } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Person[] p = new Person[n]; for (int i = 0; i < n; i++) { long t = sc.nextLong(); p[i] = new Person(t, i + 1); } Arrays.sort(p, new Comparator<Person>() { public int compare(Person a, Person b) { if (a.time != b.time) return Long.compare(a.time, b.time); return Integer.compare(a.id, b.id); } }); long total = 0; long prefix = 0; for (int i = 0; i < n - 1; i++) { prefix += p[i].time; total += prefix; } StringBuilder sb = new StringBuilder(); for (int i = 0; i < n; i++) { if (i > 0) sb.append(" "); sb.append(p[i].id); } System.out.println(sb.toString()); double avg = (double) total / n; System.out.printf("%.2f\n", avg); sc.close(); } }

Java版有一个细节：Comparator里比较long类型时，不能直接写return (int)(a.time - b.time)，因为long相减再强转int可能溢出，更稳妥的是用Long.compare()。很多人在这里栽过跟头，我特意写出来。另外输出用StringBuilder拼，比频繁print快很多，但这题n只有1000，性能差异不大，主要是养成好习惯。

关于平均值的输出格式，题目要求保留两位小数。C++用printf("%.2f")，Java用System.out.printf("%.2f")，都是老规矩。但要注意printf是四舍五入的，不是截断。比如结果是1.005，printf会输出1.01（具体取决于浮点精度），题目的验收逻辑一般也是按四舍五入来，所以直接用printf就行。

5. 容易踩的坑：WA、精度问题和边界情况排查

这题代码量那么少，看起来不像是能出问题的地方。但我这些年看过太多人在简单的题上翻车，而且翻车原因几乎一模一样。我把常见的坑逐一列出来，顺便讲清楚当时的排查思路。

5.1 等待时间算错：漏掉前缀和还是下标错位

最常见的错误是这个写法：

long long total = 0; for (int i = 0; i < n; i++) { total += p[i].time * (n - i); }

你如果手推一下就会发现，这个公式和正确的加权公式对不上。正确的加权公式是第i个人（从0开始）的耗时被重复加n-i-1次，不是n-i次。下标差1，答案就差一个数量级。这种错很难肉眼发现，因为样例可能刚好能过。我的排查方法很简单：拿样例手算一遍，把代码输出的中间量打出来，一步步核对。

还有一种错误是把总和算成了“每个人的总逗留时间”，包括自己接水的时间。题目要的是等待时间，不包含自己接水的时间。概念偷换之后答案全错。所以建议统一用前缀和来维护，prefix是从0累加到当前人之前的耗时，total是所有这些prefix的和，语义非常清楚，不容易混。

5.2 int溢出：测试数据一大就WA

我之前遇到一个情况：本地跑样例全对，交上去WA一片。后来检查发现，我把total定义成了int。当n=1000、每个Ti都很接近上限时，总等待时间大约等于Ti × n² / 2，这个量级轻松超过int。如果题面中Ti最大到10^9，那总和直接到10^15，必须long long；即便Ti只有10^3，n到10^5时也超int。所以我的习惯是：凡是和“累加、总和”相关的量，一律声明为64位整数，反正内存又不差这4个字节。

Java里对应的就是long，不要用int。Comparator里比较long字段时用Long.compare()，前面已经强调过。

5.3 输出顺序的稳定性问题

一本通版本的题目比洛谷多一个输出要求：输出排队顺序。如果两个人的接水时间相同，那么按照常理（和题目的默认预期）应当保持输入顺序。C++的sort是不稳定排序，如果只按time排序，相同时间的元素顺序不保证。解决办法有两种：

• 像我前面代码里那样，结构体里带上id，排序比较器先比time再比id，这样time相等时id小的排前面，等价于保持原始输入顺序
• 或者用stable_sort替代sort，也能保持相同time元素的相对顺序

两条路都可以，我更推荐第一种，因为使用稳定排序需要对排序算法有额外认知，而数据本身带id在后续需要输出编号时也更自然。

5.4 输出格式：行尾空格会不会被卡

本题对行尾空格通常不敏感，评测系统一般是逐token比较，但部分严格的题库或某个验证脚本可能会严格比对字符串。最安全的做法是用我上面代码里的方式：第一个编号前不输出空格，之后的每个编号前加一个前导空格。这样整行没有多余空格，格式一定正确。

另外注意输出顺序那一行是所有编号用空格分隔，不要不小心输出了换行变成多行。我就见过有人把换行符写进循环里，导致输出分成多行，直接PE（Presentation Error）。

5.5 读入数据范围：小心前导空格或EOF问题

这题输入很简单，就是先一个n，再n个正整数。用cin或Scanner都行。唯一要注意的是，如果你用getline之类的方式读行，可能把换行符吃进去，导致解析错误。这种小问题在本地测试时几乎不会遇到，但在某些在线评测环境下，输入末尾可能有额外换行，稳妥做法是用标准输入流自动跳过空白字符。

6. 从这道题延伸出去：它其实是很多高级题的“缩小版”

排队接水不是一道孤立的题，它背后的模型是“单机调度”——一台机器（一个水龙头）、多个任务（多个人）、每个任务有固定的处理时间，目标是让等待时间总和最小。这个模型在操作系统进程调度、生产流水线排程、网络请求调度等场景里到处都是，所以竞赛里它的变体非常多，经过不同包装就成了新的题。

我简单归类几个常见的变体方向：

• 多水龙头版本：如果水龙头从1个变成m个，怎么排让总等待时间最小？这就从单机调度变成了多机调度，贪心策略变成了“每次把下一个人分配到当前总耗时最短的那个水龙头”，要配合优先队列实现。

• 带权版本：如果每个人等待的时间成本不一样（比如第i个人等待1分钟的代价是w_i），那排序依据就不再是Ti，而是Ti / w_i。这个结论也是用交换论证法推出来的，你可以当作练习自己证一遍。

• 带截止时间版本：如果每个人有一个最晚开始接水的时间，超时会有惩罚，问题就变成“如何安排顺序使总延迟最小”，这对应经典的单机调度贪心，排序依据变成截止时间。

• 区间覆盖变体：如果题目把“接水时间”换成“占用区间”，要求选最多不重叠区间，那又是一道经典的贪心题，排序依据按结束时间升序。

这些变体有一个共同的思维习惯：先建立数学模型，把生活场景翻译成“谁对代价贡献了多少”，再用交换论证法尝试证明某个贪心策略是否正确，而不是上手就敲代码。很多同学刷题刷得多但遇到新题就不会，多半是跳过了“建模”这一步，直接进入“套模板”模式。所以我不建议背这道题的代码，而是建议背这道题的思考方式。

另外，这道题如果n变大了（比如10^5、10^6），排序的O(n log n)依然能扛住；如果n大到排序都吃力，那就需要转换思路。不过对一本通和洛谷这道题来说，O(n log n)完全够用，不需要额外优化。

7. 我的几个实操体会

最后聊几点个人经验，不一定写在哪本教材里，但对新手来说比较有用。

第一，遇到这种“排序后累加”的题，动手写代码前先把总等待时间的数学表达式列出来，哪怕只是草稿纸上写个∑符号，也能帮你厘清每个元素被重复计算的次数，这是最大的防错手段。

第二，代码里的中间变量能用long long就用long long，不要觉得“题面看着不大就没事”。竞赛评测的数据上限往往比你想象的狠，一个WA可能只是为了省那4个字节。

第三，多花30秒手推一遍样例。不要靠“感觉代码没问题”就提交。排队接水这道题样例给得很有代表性，手推一遍能让你对流程有真实掌握。

第四，如果你用C++，我建议把sort的比较器单独写成一个函数或结构体，不要用Lambda的简写形式（除非你非常熟悉）。这样做的原因是便于调试——当你需要打日志看排序结果时，函数里可以加输出，而Lambda里加输出很别扭。

第五，这题本质上不需要任何高级数据结构，但如果n达到10^6级别，输入输出就要注意用快读快写。C++里可以用ios::sync_with_stdio(false)关掉同步，Java里用BufferedReader或自己写FastScanner。虽然这题用不上，但养成习惯没坏处。

这道题我前前后后带过不少学生写过，从他们的代码里见过各种千奇百怪的错误。但只要理解了“短时间者优先”背后的加权和逻辑，以及交换论证的证明思路，所有错误都能自己定位。希望这篇能帮你在“排队接水”这道题上一遍过，更重要的是把贪心算法的思考范式真正装进脑子里。