解题思路

一套导弹拦截系统，每发炮弹不能高于前一发。要给所有导弹分配系统，输出每套系统拦截的导弹。

思路：贪心。

对每颗导弹：

1. 在已有的系统里找能拦下它的（系统当前高度 >= 导弹高度）
2. 找到就用这个系统拦截，更新系统的当前高度
3. 找不到就新建一套系统

为什么能拦就不新建？ 新建系统有代价，能复用就复用，系统数才能最少。

举例：8 颗导弹 389 207 175 300 299 170 158 165

• 389：新建系统1
• 207、175、170、158：系统1依次拦截
• 300、299、165：新建系统2拦截
• 所以需要 2 套系统

参考代码

#include <iostream>
using namespace std;

int a[1010][1010], k;

int main() {
    int n, x;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> x;
        int p = -1;
        for (int j = 1; j <= k; j++) {
            if (a[j][a[j][0]] >= x) {  // 系统能拦
                p = j;
                break;
            }
        }
        if (p != -1) {
            a[p][0]++;
            a[p][a[p][0]] = x;
        } else {
            k++;
            a[k][0] = 1;
            a[k][1] = x;
        }
    }

    cout << k << endl;
    for (int i = 1; i <= k; i++) {
        cout << i << ":";
        for (int j = 1; j <= a[i][0]; j++) cout << a[i][j] << " ";
        cout << endl;
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N×K)，每颗导弹检查系统
• 空间复杂度：O(N²)，存拦截序列