P4811 车辆运输（入门）

解题思路

1. 想清楚目标。 有 K 件货物、M 辆卡车，卡车可以分别装不同数量的货物，我们要用最少的卡车一次运完。直觉是：尽量让"能装得多的大卡车"先上，就像搬家时优先叫更大的车。
2. 排序。 把每辆卡车的载货件数从小到大排序，这样我们从后往前取，正好是"从大到小"地挑卡车。
3. 贪心累加。 用 sum 记录已经选中的卡车一共能装多少件货物，trucks 记录用了几辆。从载货量最大的卡车开始，一辆一辆地加入：每加入一辆，sum 就加上它的载货量，trucks 加一。
4. 判断够不够。 一旦 sum 大于等于 K，说明这些卡车已经能把所有货物装完，立刻输出 trucks 并结束本组数据。
5. 装不完怎么办。 如果从大到小全部 M 辆都选完了，sum 仍然小于 K，说明就算所有卡车一起上也运不完，输出 "NO"。
6. 多组数据。 题目有 T 组数据，每组都独立排序、独立计算，别忘了一组算完要处理下一组。

参考代码

// 车辆运输：贪心选载货量最大的卡车，从大到小依次累加，直到能装下所有K件货物
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int K, M;
        cin >> K >> M;
        int capacity[1005];   // 每辆卡车的载货件数
        for (int i = 0; i < M; i++) cin >> capacity[i];
        sort(capacity, capacity + M);   // 从小到大排序
        long long sum = 0;   // 已选的卡车一共能装多少件货物
        int trucks = 0;      // 已选的卡车数量
        bool success = false;
        for (int i = M - 1; i >= 0; i--) {   // 从大到小依次选卡车
            sum += capacity[i];
            trucks++;
            if (sum >= K) {
                success = true;
                break;
            }
        }
        if (success) cout << trucks << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

复杂度分析

每组数据先排序 O(M log M)，再从头到尾扫一遍累加 O(M)，所以每组数据的时间复杂度是 O(M log M)。T 组数据总时间是 O(T·M log M)。每组只需要一个长度不超过 M 的数组，空间 O(M)。由于 M 很小，即使 T 很大也能轻松通过。