P4792 增加饮水机（基础）

解题思路

1. 读懂题目：学校把饮水机从 1 台增加到 r 台，n 位同学排到 r 台饮水机去打水。每台饮水机前面都会排成一支队伍。要求安排顺序，让所有同学"总共花费的时间"最少。总花费时间 = 每位同学完成打水时的累计时间之和。

2. 打个比方：就像超市开了 r 个收银台。每位顾客应该去"排得最短"的那个队伍，这样大家都能尽快结账。而为了让整体更快，打水时间短的同学应该先安排，让他们尽快"腾出"机器。

3. 贪心策略：第一步，先把所有接水时间从小到大排序，让时间短的先打水；第二步，每位同学依次选择"当前累计时间最少"的那台饮水机（也就是队伍最短的），把打水时间累加上去，这位同学的完成时间就是这台机器当前的累计时间。

4. 为什么正确：时间短的先选机器，可以优先占用空闲机器；每次挑最空闲的机器，保证每台机器的"负担"尽量均匀，不让某一台特别挤。这样总完成时间最小。

5. 怎么模拟：用一个数组记录每台饮水机已经累计的时间。每位同学来了，扫一遍所有机器找出累计时间最小的那台，加上自己的时间；再把"这台机器当前累计时间"累加到总答案里。

6. 看例子：样例 n=4，r=2，时间排序后是 1,2,2,3。两台机器初始都是 0。第 1 位同学（时间1）去 1 号机，机器变成 [1,0]，花费 1；第 2 位（时间2）去 2 号机，机器变 [1,2]，花费 2；第 3 位（时间2）去 1 号机，机器变 [3,2]，花费 3；第 4 位（时间3）去 2 号机，机器变 [3,5]，花费 5。总花费 1+2+3+5=11，和答案一致。

7. 边界情况：如果 r=1，就退化成只有一台饮水机的排队问题；如果 n≤r，每个人都能独占一台机器，互不影响，总时间就是所有人接水时间之和。

参考代码

// P4792 增加饮水机：接水时间短的排前面，每人都去最空闲的饮水机
#include <iostream>
using namespace std;
int waterTime[305];     // 每位同学的接水时间
int machineBusy[105];   // 每台饮水机当前累计的忙碌时间

int main() {
    int n, r;
    cin >> n >> r;
    for (int i = 0; i < n; i++) cin >> waterTime[i];
    // 接水时间升序排序（冒泡排序，时间短的排前面）
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (waterTime[j] > waterTime[j + 1]) { int temp = waterTime[j]; waterTime[j] = waterTime[j + 1]; waterTime[j + 1] = temp; }
    long long totalTime = 0;  // 所有同学总共花费的时间
    for (int i = 0; i < n; i++) {
        // 找出当前累计时间最少的饮水机（最空闲的）
        int bestMachine = 0;
        for (int j = 1; j < r; j++)
            if (machineBusy[j] < machineBusy[bestMachine]) bestMachine = j;
        machineBusy[bestMachine] += waterTime[i];   // 这位同学到这台上接水
        totalTime += machineBusy[bestMachine];      // 这位同学的花费时间=该机累计时间
    }
    cout << totalTime << endl;
    return 0;
}

复杂度分析

排序用冒泡排序，时间 O(n²)，n≤300，很快。安排打水时，每位同学都要扫一遍 r 台机器找最空闲的，总时间是 O(n×r)，n≤300、r≤100，最多三万次运算。空间上只用了一个 305 和一个 105 大小的数组，是 O(n+r)。总体非常轻量。