从导弹拦截到贪心算法：AcWing 1010题保姆级讲解（附C++代码）

导弹拦截问题看似是一个军事领域的应用场景，实则是算法学习中一个经典的贪心算法和动态规划结合的案例。很多初学者在面对这个问题时，往往会被其实际背景所迷惑，而忽略了背后隐藏的算法本质。今天我们就来彻底拆解这个问题，看看如何从导弹拦截联想到会议安排，再到最长上升子序列，最终用简洁的代码解决这个看似复杂的问题。

1. 问题本质与算法映射

导弹拦截问题的核心可以抽象为两个部分：

1. 单系统最大拦截数量 ：即求一个序列的最长非上升子序列（Longest Non-Increasing Subsequence）
2. 全拦截最少系统数量 ：即求一个序列的最少划分，使得每个划分都是非上升序列

这实际上与计算机科学中的多个经典问题有着深刻的联系。比如：

• 会议安排问题 ：如何用最少的会议室安排所有会议
• 字符串拼接问题 ：如何用最少的字符串拼接出目标字符串
• 飞机调度问题 ：如何用最少的登机口安排所有航班

这些问题的共同特点是： 都需要在满足一定约束条件下，寻找最优的资源分配方案 。

2. 最长非上升子序列的DP解法

对于第一个问题——求单系统最大拦截数量，我们可以使用经典的动态规划方法来解决。定义一个数组 f[] ，其中 f[i] 表示以第 i 个导弹结尾的最长非上升子序列的长度。

状态转移方程为：

f[i] = max(f[i], f[j] + 1)  // 对于所有j < i且h[j] >= h[i]

这个方程的含义是：对于每个导弹 i ，我们检查前面所有比它高的导弹 j ，看看能否将 i 接在 j 后面形成更长的序列。

实际代码实现如下：

int res = 0;
for(int i = 0; i < n; i++) {
    f[i] = 1;
    for(int j = 0; j < i; j++) {
        if(h[i] <= h[j]) {
            f[i] = max(f[i], f[j] + 1);
        }
    }
    res = max(res, f[i]);
}

注意：这里的时间复杂度是O(n²)，对于n=1000来说完全足够。但如果数据规模更大，可以考虑使用二分查找优化到O(nlogn)。

3. 最少系统数的贪心解法

第二个问题——求拦截所有导弹需要的最少系统数量，才是本题的精髓所在。这个问题可以转化为： 如何用最少的非上升序列覆盖整个序列 。

贪心策略如下：

1. 维护一个数组 q[] ，记录当前每个系统能拦截的最低高度（即最后一个拦截的导弹高度）
2. 对于每个新导弹，找到第一个能拦截它的系统（即 q[k] >= h[i] 的最小 k ）
3. 如果找不到这样的系统，就新增一个系统
4. 更新对应系统的拦截高度

这个策略的正确性基于以下观察：

• 系统拦截高度数组 q[] 始终保持升序
• 每次都将新导弹放入能满足条件的最左边的系统，为后续导弹留出更多空间

代码实现：

int cnt = 0;
for(int i = 0; i < n; i++) {
    int k = 0;
    while(k < cnt && h[i] > q[k]) k++;
    if(k == cnt) {
        q[cnt++] = h[i];
    } else {
        q[k] = h[i];
    }
}

有趣的是，这个问题的答案恰好等于原序列的**最长上升子序列(LIS)**的长度。这是一个非常美妙的数学性质，也是很多算法竞赛中常考的考点。

4. 完整代码实现与解析

将上述两部分结合起来，我们得到完整的解决方案：

#include <bits/stdc++.h>
using namespace std;

const int N = 1010;
int h[N], f[N], q[N];
int n;

int main() {
    string line;
    getline(cin, line);
    stringstream ss(line);
    
    while(ss >> h[n]) n++;
    
    // 第一部分：求最长非上升子序列
    int max_len = 0;
    for(int i = 0; i < n; i++) {
        f[i] = 1;
        for(int j = 0; j < i; j++) {
            if(h[i] <= h[j]) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        max_len = max(max_len, f[i]);
    }
    
    // 第二部分：求最少系统数
    int sys_cnt = 0;
    for(int i = 0; i < n; i++) {
        int pos = 0;
        while(pos < sys_cnt && h[i] > q[pos]) pos++;
        if(pos == sys_cnt) {
            q[sys_cnt++] = h[i];
        } else {
            q[pos] = h[i];
        }
    }
    
    cout << max_len << endl << sys_cnt << endl;
    return 0;
}

代码中的几个关键点：

1. 输入处理 ：使用 stringstream 处理可能含有不定数量整数的输入行
2. 双问题求解 ：分别计算最大拦截数量和最少系统数量
3. 数组复用 ： q[] 数组既用于记录系统状态，又不需要额外初始化

5. 算法优化与扩展思考

虽然上述解法已经能够AC本题，但我们还可以进一步思考优化空间：

1. 二分查找优化 ：对于最长上升子序列问题，可以使用二分查找将时间复杂度从O(n²)降到O(nlogn)

   优化后的查找部分代码：

   int pos = lower_bound(q, q + sys_cnt, h[i]) - q;
   

2. 统一解法 ：注意到两个问题其实都是关于子序列的，可以尝试寻找更统一的解法

3. 实际问题扩展 ：考虑导弹拦截系统的其他变种，比如：

   • 系统有启动延迟
   • 导弹有不同的威胁值
   • 拦截有成功率限制

这些扩展问题在ACM/ICPC等竞赛中经常出现，理解基础问题的本质有助于解决更复杂的变种。