中 · 贪心
排队打水
排第一的人不让任何人等；排最后的人让所有人都等。一个人接水的每一分钟，都由身后所有人埋单 —— 所以最省的队列，是把小时间放在被乘次数最少的位置。
一句话答案升序排序后累加：第 i 个人等的是前面所有人的总和。排序后 <code>total += wait; wait += a[i]</code> 就是全部解法。
题目
输入: 第一行是 n（1 ≤ n ≤ 100）。第二行 n 个整数（1 ≤ a ≤ 1000）：每人接水要用的秒数。
输出: 最小可能的总等待时间。一个人的等待时间 = 轮到自己之前的一切等待（自己接水的时间不算）。
样例:
| 输入 | 输出 |
|---|---|
4 | 8 |
1 | 0 |
样例里最好的顺序是 1、1、3、4：等待分别是 0、1、2、5 —— 合计 8。其他任何顺序都要多付；可以证明排序后的顺序就是最小值。
你的解答
「运行我的输入」用的自定义输入
判题在浏览器本地运行。死循环会在 3 秒后被自动中断 —— 但还是确保每个循环都有出口。代码随打随存。
卡住了？提示
提示 1 — 写下交换改变了什么
取相邻的两人 x 在前 y 在后，想象交换。只有这两个人的等待时间变了：x 先行时两人共付 y，y 先行时共付 x。当 y < x 时交换更优 —— 所以最优队列里每对相邻都升序，整条队列必然有序。这就是交换论证 —— 它让贪心从「碰运气」变成「可证明」。
提示 2 — 扫描就是滚动的前缀
排序后，第 i 个人等的是 a[0..i-1] 的和。不用内层循环，带着 wait 走：按顺序对每个人 total += wait; 然后 wait += a[i];。每人两次加法，没有第二层循环 —— 和 区间求和 同一个前缀思路。
提示 3 — 等待在开始之前，不是之后
题面说自己的接水时间不算等待。滚动前缀的写法天然就对 —— 但如果你把 a[i] 也加进前缀再计入，所有答案都会偏大 Σa[i]，而且这个 bug 藏在一个看起来很合理的数字里。
题解（先自己试试！）
#include <iostream>
using namespace std;
int a[105];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (a[j] > a[j + 1]) {
int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
}
}
}
long long total = 0, wait = 0;
for (int i = 0; i < n; i++) {
total += wait;
wait += a[i];
}
cout << total << endl;
return 0;
}这就是操作系统里的「短作业优先」，用四行交换论证证明。它的姐妹你已见过：最少硬币数 是另一种证明的贪心，冒泡排序 是两者共用的机器。当某个贪心感觉对时，练习永远是同一件事：找到能让任何非有序答案变得更好的那次交换。
深度解析
为什么这样做对
交换论证:取任何非升序的队列,交换一对相邻的逆序(x 在前 y 在后且 y < x)。只有这两个人的等待变了,而且总共减少 x − y。所以未排序的队列总能被改进,唯一的局部最优就是有序 —— 这是证明,不是祈祷。
代价
冒泡排序 O(n²),扫描 O(n);n ≤ 100 时约一万次比较。总等待轻松装进 64 位(100 人 × 1000 秒 ≈ 500 万秒)。
常见错法
- 把每人自己的接水时间也算进等待,所有答案都会偏大 Σa[i] —— 扫描必须先
total += wait再wait += a[i]。 - 排序的是一份拷贝、扫描的却是原数组(或反之)—— 答案悄悄既不对应这个顺序也不对应那个。
- 相等的时间彼此之间任意排都行:平局是免费的,别为它们把排序写复杂。
记住这两句
- 快的先来:排在前面的人,每一分钟都由身后所有人埋单。
- 交换论证 = 贪心的证明模板:找到能让任何非有序答案变好的那次交换。
🐞 这段是错的 —— 点开,亲手让它挂一次
按到来顺序扫描 —— 队列根本没排过序
#include <iostream>
using namespace std;
int a[105];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
long long total = 0, wait = 0;
for (int i = 0; i < n; i++) { // bug: no sorting first
total += wait;
wait += a[i];
}
cout << total << endl;
return 0;
}