解题思路

一共 4 堆胡萝卜，每堆只能拿 1 根，想让 4 根胡萝卜的总重量最大。

很自然就会想到：每堆都拿最重的那一根！这样每堆都贡献了它最大的可能，4 个“最大”加起来当然就是能拿到的最大总重量。这种“每一步都做当前看起来最好的选择”的方法，就叫贪心。

为什么每堆拿最重的就是对的？因为 4 堆之间互不影响：这一堆拿哪根，不会影响其他堆。所以每一堆都拿自己最重的，整体就一定是最大的。

做法：

1. 对每一堆（一共 4 堆），读入 n 和 n 个重量，找出这堆的最大值 mx；
2. 把 4 个 mx 加起来；
3. 输出总和。

参考代码

// P4459 贪心的小童：每堆胡萝卜只能拿1根，要总重量最大，就在每堆里挑最重的那根
#include <iostream>
using namespace std;

int main() {
    int total = 0;
    for (int k = 0; k < 4; k++) { // 一共有4堆
        int n, x;
        cin >> n;
        int mx = 0; // 本堆最重的胡萝卜重量
        for (int i = 0; i < n; i++) {
            cin >> x;
            if (x > mx) mx = x; // 更新本堆最大值
        }
        total += mx; // 拿本堆最重的这一根
    }
    cout << total << endl;
    return 0;
}

复杂度分析

• 每堆扫一遍找最大值，共 4 堆，每堆最多 1000 根胡萝卜，时间复杂度是 O(n)（n 表示每堆的数量）。
• 只用了一小把变量，空间复杂度是 O(1)。