跳到主要内容

AcWing 913. 排队打水

本节目标

用短作业优先最小化所有顾客的总等待时间。

这是贪心选择与证明中最直接的相邻交换论证：服务时间短的顾客放在前面，会减少其后所有人的等待。

题意与约束​

给定每位顾客打水所需时间，所有顾客排成一队依次服务。某人等待时间是其前面所有服务时间之和，求最小总等待时间。

直接思路与瓶颈​

枚举所有队列顺序有 n! 种。虽然每个排列都能计算等待和，但排列数量很快超过可接受范围。

贪心模型与算法推导​

按服务时长升序排序，扫描时维护已服务总时长 elapsed。当前顾客的等待就是 elapsed，加入总和后再将自己的时长加到 elapsed。中间和使用 long long，避免总等待时间溢出。

正确性依据​

设相邻两位顾客服务时长为 a>b，此前已经等待的总时长为 P。顺序 a,b 对这两人的等待贡献为 P+(P+a)，交换为 b,a 后为 P+(P+b)，后者少 a-b。所以任何逆序对交换后都不会变差，持续交换可得到短作业优先的最优排列。

样例执行过程​

[1,2,3] 已有序。elapsed=0 时加入等待 0；服务 1 后 elapsed=1，加入 1；服务 2 后加入 3，总和为 4。只有一位顾客时其前方为空，答案为 0。

代码实现​

C++17
#include <algorithm>
#include <vector>

using namespace std;

long long minWaitingTime(vector<int> durations) {
    sort(durations.begin(), durations.end());

    long long elapsed = 0;
    long long total = 0;
    for (int duration : durations) {
        total += elapsed;
        elapsed += duration;
    }
    return total;
}

复杂度分析​

排序耗时 O(n log n)，扫描 O(n)；额外空间除排序外为 O(1)。

边界与易错点​

  • 总等待时间不是所有服务时间之和；第一位顾客等待为零。
  • 计算 elapsed 和 total 时使用宽整数。
  • 相同服务时间的顾客交换不会影响答案。

模式迁移​

当每个任务权重相同且目标是等待时间和时使用短作业优先；若任务有不同权重，排序键会变为比值或需要更复杂的调度模型。