P4805 割水稻（基础）

解题思路

1. 读懂题目：有 n 位农民伯伯要割水稻，但只有 r 把镰刀，所以大家要轮流用。一位农民的收获时间 = 等待时间 + 自己的收割时间。我们要安排使用顺序，让所有农民的总收获时间最少。

2. 打个比方：这和排队答疑一模一样！收割快的人先用镰刀，后面的人就少等一会儿，总收获时间就最短。

3. 第一步：把每位农民的收割时间从小到大排序，收割时间短的排在前面。

4. 第二步：用一个数组记录每把镰刀当前已经排队的累计时间，初始都是 0。

5. 第三步：从第一位农民开始，每次在 r 把镰刀里找"累计时间最少"的那把镰刀给他用。

6. 第四步：这位农民的收获时间 = 镰刀当前累计时间 + 自己的收割时间，累加到总时间里，再更新那把镰刀的累计时间。

7. 为什么贪心正确：收割时间短的任务先安排，能让后面的人更早开始收割；新任务排到更空闲的镰刀上，整体等待时间最少，总收获时间就最小。

8. 边界情况：如果镰刀数量 r 不少于农民人数 n，每个人都马上能用上镰刀，总收获时间就是所有 ti 的和；如果只有 1 位农民，总时间就是他的收割时间。

参考代码

// P4805 割水稻：收割时间短的先割，哪把镰刀空闲就先排到哪，求最少总收获时间
#include <iostream>
#include <algorithm>
using namespace std;

int cut[405];         // 每位农民伯伯的收割时间
long long load[205];  // 每把镰刀目前已经排队的累计时间

int main() {
    int n, r;
    cin >> n >> r;
    for (int i = 0; i < n; i++) cin >> cut[i];
    // 收割时间短的先安排，能减少后面农民的等待
    sort(cut, cut + 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] + cut[i];
        load[best] += cut[i];
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

排序需要 O(n log n)；安排每位农民时要在 r 把镰刀里找累计时间最少的一把，需要 O(r)，所以总时间 O(n log n + n·r)。题目保证 n ≤ 400、r ≤ 200，非常快。空间上需要一个长度 r 的数组，空间复杂度是 O(r)。