P4803 节省时间2（基础）

解题思路

1. 读懂题目：学校有 2 位老师答疑，每位同学的"答疑完成时间"等于他自己的答疑时间加上等他前面同学的累计时间。我们要安排好排队顺序，让所有同学完成时间的总和最少。

2. 打个比方：就像去银行取号排队，办得快的顾客先办，后面的人就能少等一会儿，整体等的时间最少。

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

4. 第二步：用两个变量分别记录两位老师目前已经排队的累计时间，初始都是 0。

5. 第三步：从第一位同学开始，每次都让这位同学排到"当前累计时间少"的那位老师后面。

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

7. 为什么贪心正确：答疑时间短的任务先安排，能让后面的人更早开始答疑；新同学排到更空闲的老师，整体等待时间最少，这保证了总完成时间最小。

8. 边界情况：如果只有 1 位同学，答案就是他的答疑时间；如果两位同学答疑时间相同，谁先谁后都不影响总时间。

参考代码

// P4803 节省时间2：答疑时间短的排前面，哪位数老师空闲就排到哪，求最少总完成时间
#include <iostream>
#include <algorithm>
using namespace std;

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

int main() {
    int n;
    cin >> n;
    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;
        if (load[1] < load[0]) best = 1;
        // 这位同学的完成时间 = 等前面同学的时间 + 自己的答疑时间
        ans += load[best] + need[i];
        load[best] += need[i];
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

排序需要 O(n log n) 的时间，排序后扫描 n 位同学、每次比较两位老师，是 O(n)。题目保证 n ≤ 400，所以非常快。空间上只用了两个老师累计时间的变量，空间复杂度是 O(1)。