P4804 节省时间3（基础）

解题思路

1. 读懂题目：这次学校有 r 位老师答疑，n 位同学排队。每位同学的答疑完成时间 = 自己的答疑时间 + 等前面同学的累计时间。要输出 n 位同学的平均花费时间，保留两位小数。

2. 打个比方：就像食堂开了多个窗口，同学们应该按答疑时间从短到长排队，并且新来的同学排在"目前队伍累计时间最少"的窗口，这样整体等的时间最少。

3. 第一步：把每位同学的答疑时间从小到大排序，答疑时间短的同学排在前面。

4. 第二步：用一个数组记录每位老师当前已经排队的累计时间，初始全是 0。

5. 第三步：从第一位同学开始，每次在 r 位老师里找"累计时间最少"的那位老师，让这位同学排到他后面。

6. 第四步：这位同学的完成时间 = 老师当前累计时间 + 自己的答疑时间，累加到总时间里，再更新那位老师的累计时间。

7. 第五步：全部安排完后，平均花费时间 = 总时间 ÷ n。输出时用 fixed + setprecision(2) 保留两位小数。

8. 注意：保留两位小数一定要用浮点数的格式化输出，不要在程序里自己手工四舍五入。因为有些数据的平均值正好卡在边界上，评测数据是按浮点格式化的规则判断的。

9. 边界情况：如果老师人数 r 不少于学生人数 n，每位同学都能马上被答疑，平均时间就是所有 ti 的和除以 n；如果只有 1 位同学，平均时间就是他的答疑时间。

参考代码

// P4804 节省时间3：r位老师答疑，答疑时间短的先排，求平均花费时间保留两位小数
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;

int need[405];          // 每位同学的答疑时间
long long load[205];    // 每位老师目前已经排队的累计时间

int main() {
    int n, r;
    cin >> n >> r;
    for (int i = 0; i < n; i++) cin >> need[i];
    // 答疑时间短的先排，让更多人早点完成
    sort(need, need + n);
    long long ans = 0;   // 所有同学答疑完成时间的总和
    for (int i = 0; i < n; i++) {
        // 找当前排队时间最少的那位老师
        int best = 0;
        for (int k = 1; k < r; k++) {
            if (load[k] < load[best]) best = k;
        }
        // 完成时间 = 等前面同学的时间 + 自己的答疑时间
        ans += load[best] + need[i];
        load[best] += need[i];
    }
    // 平均花费时间 = ans / n，保留两位小数输出
    cout << fixed << setprecision(2) << (double)ans / n << endl;
    return 0;
}

复杂度分析

排序需要 O(n log n)；安排每位同学时要在 r 位老师里找累计时间最少的一位，需要 O(r)，所以总时间 O(n log n + n·r)。题目保证 n ≤ 400、r ≤ 200，完全够快。空间上需要一个长度 r 的数组记录老师累计时间，空间复杂度是 O(r)。