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

从导弹拦截到贪心算法AcWing 1010题深度解析与实战导弹拦截问题看似是一个军事领域的应用场景实则是算法学习中一个极具代表性的案例。这道题目巧妙地将现实问题抽象为两个核心算法问题最长非上升子序列和贪心策略下的系统分配。对于正在准备算法竞赛的选手来说理解这道题的解法不仅能掌握两种重要算法思想更能培养将实际问题转化为数学模型的能力。1. 问题背景与算法建模导弹拦截问题描述了一个典型的资源分配场景一套拦截系统每次发射的拦截高度不能高于前一次这意味着我们需要找到导弹高度序列中的最长非上升子序列来回答最多能拦截多少导弹而最少需要多少套系统则转化为一个序列覆盖问题。为什么这个问题值得深入研究它完美展示了如何将现实约束转化为算法条件同时考察了动态规划和贪心算法两种重要思想解法中隐藏着对Dilworth定理的直观理解代码实现简洁但思维密度高在实际比赛中这类一题多解的问题往往能区分选手的算法素养。理解其本质后可以举一反三应用到股票交易、任务调度等多种场景。2. 最长非上升子序列的动态规划解法第一个问题的标准解法是动态规划。给定高度序列h定义f[i]为以第i个导弹结尾的最长非上升子序列长度状态转移方程为f[i] max(f[i], f[j] 1) 对于所有j i且h[j] h[i]这个O(n²)的解法是线性DP的经典应用。但我们可以进一步优化理解逆向思维将问题看作寻找最长的下降序列边界处理每个导弹至少可以单独拦截所以初始值f[i]1结果提取最终结果是所有f[i]中的最大值实际代码实现时可以结合输入处理的技巧string s; getline(cin, s); stringstream ssin(s); while(ssin h[n]) n; // 读取不定长输入3. 贪心算法求解最少系统数第二个问题才是本题的精髓所在。我们需要找到覆盖所有导弹的最少非上升子序列数这等价于求该序列的最长上升子序列长度——这就是著名的Dilworth定理的应用。贪心策略的核心维护一个数组q其中q[i]表示第i套系统当前能拦截的最低高度对于每个导弹找到第一个能拦截它的系统即q[k]≥当前高度如果没有合适的系统则新增一套这个过程的巧妙之处在于数组q始终保持有序这是高效查找的基础替换策略保证最优性用当前导弹高度替换找到的q[k]为后续拦截保留更大空间时间复杂度O(nlogn)通过二分查找可以进一步优化关键代码段解析int k 0; while(k cnt h[i] q[k]) k; // 查找第一个能拦截的系统 if(k cnt) q[cnt] h[i]; // 新增系统 else q[k] h[i]; // 更新系统状态4. 算法对比与实战优化将两种解法放在一起对比能更深入理解问题本质特性动态规划解法贪心解法解决的问题最长非上升子序列最少系统数时间复杂度O(n²)O(n²)或O(nlogn)空间复杂度O(n)O(n)算法思想动态规划贪心算法关键操作双重循环比较维护单调序列理论依据最优子结构Dilworth定理实战优化技巧输入处理使用stringstream处理不定长输入更鲁棒二分查找优化将线性查找改为二分查找提升效率变量复用合理复用数组空间减少内存使用边界检查特别注意空输入和单元素情况优化后的查找部分代码示例int l 0, r cnt - 1; while(l r) { int mid (l r) 1; if(q[mid] h[i]) r mid; else l mid 1; } if(q[l] h[i]) q[l] h[i]; else q[cnt] h[i];5. 从具体到抽象的算法思维训练这道题的真正价值在于培养算法建模能力。我们可以总结出解决类似问题的通用思路问题分析明确约束条件和优化目标模型转化将现实约束转化为数学条件算法选择识别问题类型选择合适的算法范式优化验证分析算法正确性和效率代码实现用简洁高效的代码表达算法思想常见误区与调试技巧混淆上升子序列和非上升子序列的条件判断贪心算法正确性的证明困难边界条件处理不当导致数组越界输入输出格式不符合题目要求调试时可以使用的测试用例测试输入1100 90 80 70 60 50 预期输出6 1 测试输入21 2 3 4 5 6 预期输出1 6 测试输入3389 207 155 300 299 170 158 65 预期输出6 26. 扩展应用与变种问题掌握这个模型后可以解决一大类相似问题股票交易问题最多k次交易的最大收益任务调度问题最少机器完成所有任务序列覆盖问题将序列划分为若干特定子序列二维版本考虑导弹的飞行时间和高度两个维度例如LeetCode上的类似题目300.最长递增子序列354.俄罗斯套娃信封问题646.最长数对链每种变种都考验着对核心算法的灵活运用能力。建议在理解本题后尝试解决这些扩展问题以巩固学习效果。