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

想象你是一名防空指挥官，面对屏幕上不断跳动的导弹高度数据，必须快速决策：如何用最少的拦截系统击落所有目标？这不仅是军事难题，更是算法竞赛中的经典考题。本文将用导弹防御的实战场景，带你彻底掌握动态规划与贪心算法的精髓。

1. 问题拆解：导弹拦截的双重挑战

题目看似简单，实则暗藏两个关键子问题：

1. 单系统最大拦截量 ：求导弹高度序列的最长非递增子序列（LNDS）
2. 最少系统需求 ：求能将所有导弹分成的最少非递增子序列数

这两个问题分别对应着动态规划和贪心算法的典型应用场景。我们先从实际问题抽象出数学模型：

给定序列H = [h₁, h₂, ..., hₙ]，需要：

• 找出H的最长子序列，满足hᵢ ≥ hⱼ（当i < j）
• 将H划分为最少数量的非递增子序列

输入样例解析 ：

389 207 155 300 299 170 158 65

对应的最优解是：

• 最长非递增子序列：389, 300, 299, 170, 158, 65（长度6）
• 最少系统数：2（系统1：389, 207, 155；系统2：300, 299, 170, 158, 65）

2. 动态规划解法：最长非递增子序列

2.1 基本思路

定义f[i]为以第i个导弹结尾的最长非递增子序列长度。状态转移方程为：

f[i] = max(f[j] + 1) ∀j < i且h[j] ≥ h[i]

2.2 关键代码解析

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的数据规模完全足够。

2.3 优化思路

对于更大规模数据，可以考虑：

• 二分查找优化到O(nlogn)
• 使用树状数组维护前缀最大值

3. 贪心算法解法：最少拦截系统

3.1 算法核心

维护一个数组q，其中q[i]表示第i个系统当前能拦截的最低高度。对于每个导弹：

1. 在所有q[k]≥h[i]的系统中，选择q[k]最小的进行拦截
2. 如果没有可用系统，则新增一个系统

3.2 代码实现细节

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];
    }
}

关键点：q数组始终保持升序排列，这使得我们可以用简单的线性搜索找到合适的位置。

3.3 算法正确性证明

这实际上是Dilworth定理的应用：将序列划分为最少非递增子序列的数量等于最长递增子序列的长度。在样例中：

• 最长递增子序列：155, 300（长度2）
• 最少系统数确实为2

4. 两种算法的对比与选择

特性	动态规划解法	贪心算法解法
时间复杂度	O(n²)	O(n²)
空间复杂度	O(n)	O(n)
适用问题	最长非递增子序列	最少系统划分
扩展性	可优化到O(nlogn)	难以进一步优化
实际应用	数据分析	资源分配

选择建议 ：

• 当只需要求最长非递增子序列时，优先使用动态规划
• 当需要完整划分方案时，贪心算法更合适
• 在竞赛中，通常需要同时解决两个问题

5. 实战技巧与常见错误

5.1 输入处理技巧

题目输入是一行不定长的数字，推荐使用stringstream处理：

string s;
getline(cin, s);
stringstream ssin(s);
while(ssin >> h[n]) n++;

5.2 边界条件

• 空输入处理
• 所有导弹高度相同的情况
• 严格递减序列的情况

5.3 调试建议

可以打印中间变量观察算法执行过程：

cout << "Processing missile " << i << " height=" << h[i] << endl;
cout << "Current systems: ";
for(int k=0; k<cnt; k++) cout << q[k] << " ";
cout << endl;

6. 扩展应用与变种问题

6.1 类似题目推荐

• LeetCode 300. 最长递增子序列
• AcWing 896. 最长上升子序列 II
• Codeforces 340D. Bubble Sort Graph

6.2 实际问题映射

• 任务调度中的资源分配
• 网络数据包的处理顺序控制
• 股票交易中的波段识别

在最近的项目中，我发现这种贪心策略特别适合处理实时数据流的分组问题。比如在物联网设备监控中，将传感器数据按特定规则分组处理时，完全可以使用相同的算法框架。