跳至正文

1 条题解

  • 0
    @ 2026-10-8 19:19:22

    【本题解由站长编写】

    排队打水最短总时间:把所有人按打水时间从小到大排序,再依次轮流分配到 r 个水龙头上(第 i 个人用 i % r 号龙头)。总时间 = Σ 每个人的「等待 + 自己的打水时间」,用 finish[k] 记录第 k 个龙头累计用时,累加 finish[k] 即可。装水时间短的人先开始能使总等待最短(交换论证:若 t_a > t_b 却 a 在 b 前,交换后总时间更小)。

    代码(C++17)

    #include <bits/stdc++.h>
    using namespace std;
    
    int main() {
        int n, r;
        cin >> n >> r;
        vector<int> t(n);
        for (int &x : t) cin >> x;
        sort(t.begin(), t.end());
        vector<long long> finish(r, 0);
        long long total = 0;
        for (int i = 0; i < n; i++) {
            int k = i % r;
            finish[k] += t[i];
            total += finish[k];
        }
        cout << total << endl;
        return 0;
    }
    
    • 1

    信息

    ID
    4180
    时间
    1000ms
    内存
    256MiB
    难度
    6
    标签
    递交数
    0
    已通过
    0
    上传者