解题思路

导弹拦截系统有个特点：一发系统拦截的导弹高度必须越来越低。要求用最少的系统拦截所有导弹。

贪心思路：每颗导弹，尽量用已有系统拦，拦不了再新建。

对每颗导弹：

1. 在已有的所有系统里找，看哪个系统的当前高度还能拦下这颗导弹
2. 如果找到，就用这个系统拦，并把它的当前高度更新成这颗导弹的高度（因为之后只能拦更低的）
3. 如果一个系统都没有，就新建一套系统

为什么能拦截就尽量不新建？ 因为新建系统是有代价的（多一套），能复用就复用，这样才能让系统总数最少。

举例：导弹高度 389 207 175 300 299 170 158 165

• 389：没系统，新建系统1（高度389）
• 207：系统1能拦，更新为207
• 175：系统1能拦，更新为175
• 300：系统1（175）拦不了，新建系统2（300）
• 299：系统2能拦，更新为299
• 170：系统1能拦，更新为170
• 158：系统1能拦，更新为158
• 165：系统1（158）拦不了，系统2（299）能拦，更新为165
• 共 2 套系统

参考代码

#include <iostream>
using namespace std;

int n, k, p, x, a[1100];

int main() {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> x;
        p = 0;

        // 在已有系统里找能拦下这颗导弹的
        for (int j = 1; j <= k; j++) {
            if (a[j] >= x) {
                p = j;
                break;
            }
        }

        if (p == 0) {  // 没有系统能拦，新建
            k++;
            a[k] = x;
        } else {  // 用已有系统拦，更新高度
            a[p] = x;
        }
    }

    cout << k;
    return 0;
}

复杂度分析

• 时间复杂度：O(N×K)，每颗导弹检查已有系统
• 空间复杂度：O(N)，存各系统当前高度