贪心：排队接水

$n$ 个人排队用一个水龙头，每人接水时间不同，排在后面的人要等前面所有人接完。问怎么排，让所有人的总等待时间最小。策略：接水快的人排前面，即按用时从小到大排序。

sort(t, t + n);              // 用时从小到大
long long wait = 0, pre = 0;
for (int i = 0; i < n; i++) {
    wait += pre;             // 第 i 个人要等前面所有人的总时间
    pre  += t[i];            // 累加前缀，供后面的人等待
}

为什么快的先打？因为排在第 1 位的人的用时，会被后面 $n-1$ 个人都等一遍；排第 2 位的被等 $n-2$ 遍……越靠前的用时被重复计算的次数越多。要让总等待小，就得让"被乘的次数多"的位置放"最小"的用时。

总等待时间 $=\sum t_i\cdot (n-i)$，排序后取到最小。坑：总和要用 long long；题目问的是"总等待"还是"平均等待"，别看漏。复杂度 $O(n\log n)$。