企业官网建设流程全解析

1. 问题到底是什么：经典拦截模型的两种需求

要说贪心算法里最有画面感的入门题，导弹打飞机这个模型绝对排得上号。它最早是个经典的拦截系统题目，设定很简单：某个防御系统拦截来袭导弹，第一发炮弹可以拦截任意高度的目标，但之后每一发炮弹的高度都不能超过前一发。相当于一套系统能打出的拦截高度序列是“一路往下走，只能持平或变矮，不能反弹”。给定一串来袭导弹的高度序列，问你两个事：一套系统最多能拦下几枚导弹，以及要拦下全部导弹，最少得部署几套系统。

先强调一点，这道题很多人一上来就被“导弹”两个字带偏思路，以为要写什么复杂的模拟器，实际上它考察的就是序列上的两个经典问题。第一问本质是求最长不上升子序列长度，属于动态规划的主场；第二问看起来像系统调度，实际上贪心就能解决，而且答案和一个非常经典的定理绑定在一起。把这两个问题拆开看，你就明白为什么这题被那么多算法课拿来当贪心的标准案例了。

这题适合什么人看？如果你是刚接触贪心算法的同学，或者刷题刷到序列DP想巩固一下边界处理，这篇内容可以直接照搬思路和代码。哪怕你暂时不刷竞赛题，工作中偶尔做调度方案、任务分配、资源池管理，也会发现这套贪心逻辑非常眼熟。

我拿一组具体数据来走一遍全流程，后面所有推导、代码、坑点都围绕它展开：

来袭导弹高度（按到达顺序）：389 207 155 300 299 170 158 65

用这套数据手动推一遍，比干看十遍理论都管用。

2. 先解第一问：一套系统最多拦截多少枚

2.1 动态规划的基础写法

一套系统要求拦截序列高度单调不增，也就是允许 389 -> 207 -> 155 -> 65 这种一路走低的链路。那问题就变成了：在这个序列里找一条最长的“不上升”路径。

最直接的做法是定义dp[i]表示“以第 i 枚导弹为结尾时，最多能拦截多少枚”。对每个 i 往前扫描所有 j < i，只要a[j] >= a[i]，就说明第 i 枚可以跟在第 j 枚后面，于是dp[i] = max(dp[i], dp[j] + 1)。最后把所有 dp 值取最大就是答案。

这个写法的时间复杂度是 O(n^2)。平时刷题学习完全没问题，理解上也很直观。但我把丑话说在前面，如果你遇到的是竞赛版题目，n 可能直接给到 100000，O(n^2) 稳稳超时。所以必须会优化版。

2.2 二分优化：d 数组到底存什么

O(n log n) 的优化思路是这样的：维护一个数组 d，d[k]表示“长度为 k 的不上升子序列中，结尾元素能取到的最大值”。注意这里存的是“最大”，因为对于不上升序列来说，结尾越大，将来越容易继续接更小的数，也就是越有扩展潜力。

遍历导弹高度时，对每个新高度 x，在 d 数组里找到第一个小于 x 的位置，然后把该位置更新为 x。为什么找“第一个小于 x”的位置？因为你希望找到一个长度最长的序列，让它能接上 x，且接上之后保持不上升。如果 d 中某个位置的结尾已经小于 x 了，那 x 接上去就会破坏不上升性质，所以必须找到那个临界点，把它的结尾更新成 x。

这里有个新手必踩的坑：查找的时候用的是“第一个小于 x 的位置”，而不是“第一个小于等于 x 的位置”。因为问题允许相等高度连续拦截，等于的关系是合法的，不能把等于的情况拆掉。到了第二问你会看到类似但相反的边界逻辑，所以先把这个点记牢。

我拿第一个 case 手动跑一遍。原始高度 389 207 155 300 299 170 158 65，d 数组变化过程是这样的：

x=389：d = [389] x=207：207 < 389 结尾，可以接在 389 后面，序列长度 2，d = [389, 207] x=155：155 < 207，可以再接，长度 3，d = [389, 207, 155] x=300：找到第一个小于 300 的位置，d[1]=389 不小于，d[2]=207 小于 300，把 d[2] 更新为 300，d = [389, 300, 155] x=299：第一个小于 299 的位置在 d[3]=155，更新为 299，d = [389, 300, 299] x=170：170 小于 299，可以在 299 后面继续接，长度 4，d = [389, 300, 299, 170] x=158：158 < 170，长度 5，d = [389, 300, 299, 170, 158] x=65：65 < 158，长度 6，d = [389, 300, 299, 170, 158, 65]

最终 d 的长度是 6，所以一套系统最多能拦截 6 枚。你可以自己验证一下，389 -> 300 -> 299 -> 170 -> 158 -> 65 这条链就是一条合法的最长不上升子序列。

注意：d 数组最终的序列并不一定是真正的拦截方案本身，它只是记录了“每个长度对应的最优结尾”。如果题目要求输出具体拦截序列，得额外记录转移路径，那是另一套写法。竞赛里大部分时候只问长度，所以这个细节常被忽略，但做工程题就要多留一个心眼。

3. 第二问：最少需要几套系统——贪心算法的重头戏

3.1 贪心策略：维护一张“最后高度”表

第一问解决之后，第二问才是真正体现贪心价值的地方。现在要求所有导弹都必须被拦下来，每个系统同样遵守“高度只能持平或变矮”的规则，问最少要开几套系统。

先把最容易想到的贪心方案说出来：每来一枚导弹，在已有系统里找出“最后拦截高度大于等于当前导弹高度”的那些系统，从中选择最后高度最小的那个系统去拦截。如果所有系统的最后高度都小于当前导弹高度，说明现有系统谁都接不住，就新开一套。

这个策略在行内有个通俗说法：“能接就接，但必须接在最近够得着的系统上”。再翻译成人话：你手头有几个垃圾桶，每个垃圾桶只能放越来越矮的东西，新东西来了，扔进哪个桶？挑桶口标高最低、还能放得下的那个桶。这样能最大程度保留那些“高度还比较高的桶”，把它们留给后面可能出现的更高导弹。

3.2 为什么选择“最后高度最小且够得着”的系统

这个“最小且够得着”的选择，就是贪心算法的精髓。可以用一个简单场景来体会：当前有两套系统，最后高度分别是 300 和 200，此时来了一枚高度 250 的导弹。两套都够得着，但如果让 300 这套去接，它之后变成 250，和 200 那套高度差距变小了；如果让 200 这套去接，它变成 250，反而比之前高了，直接浪费了一个低位。所以正确选择是让 200 这套接，把 300 那套留作高位预备。

来回推理其实就是一条核心原则：每次操作都要让系统集合的状态“尽量差”，把好牌留在后手。这和打牌出小牌留大牌是同一个道理。

实现的时候直接用一个数组存每套系统的最后拦截高度。每来一个新导弹，就在这个数组里找第一个大于等于它的位置，如果找到了就更新那个位置；找不到就在末尾追加一个当前高度，代表新开系统。

3.3 和最长上升子序列的奇妙等价关系

这个贪心的答案，实际上就等于原始序列的最长严格上升子序列长度。第一次知道这个结论时我挺惊讶的，后来理解了就不觉得奇怪：每套系统本质上是把原序列拆成若干个不上升子序列，而这个“最少能拆成几个不上升子序列”恰好等于“最长上升子序列的长度”。这就是组合数学里 Dilworth 定理的一个特例。

通俗解释一下：如果有一串上升的导弹，比如 100 -> 200 -> 300，那任何一套系统都只能拦住其中一枚，因为系统高度不能反弹。所以上升序列有多长，至少就需要多少套系统。反过来，用上一节说的贪心策略，又能证明这个下界一定可以达到。所以第二问的答案在数值上就等于最长严格上升子序列长度。

这里有个很关键的等号细节：第二问和“最长严格上升子序列”对应，注意“严格”二字。如果求的是最长不上升子序列，用“第一个小于”；求最少系统数，对应“最长严格上升”时，查找用的是“第一个大于等于”。两个边界常常被搞反，后文第 5 节专门展开讲。

为了验证，还是用那组数据跑一遍第二问的贪心过程：

x=389：没有系统，新开一套 S1，最后高度 389 x=207：S1 高度 389 够得着，更新 S1=207 x=155：S1 高度 207 够得着，更新 S1=155 x=300：S1=155 不够，新开 S2=300 x=299：S2=300 够得着，更新 S2=299 x=170：S1=155 不够，S2=299 够得着，更新 S2=170 x=158：S1=155 不够，S2=170 够得着，更新 S2=158 x=65：S1=155 够得着，更新 S1=65

最终用了 2 套系统。你再看原始序列的最长严格上升子序列：155 -> 300 或者 155 -> 299 甚至 170 -> 299？最长严格上升子序列是 155 -> 300 或 155 -> 299 这种长度 2 的，当然这里 389 太小不构成更长的上升链。答案是 2，完全对上。

4. 完整代码实现与验证

4.1 C++ 代码：一份代码解两个问题

第一问和第二问虽然思路不同，但代码结构非常相似，核心就是一个二分查找。C++ 里直接用upper_bound和lower_bound就能省去手写二分。

#include <bits/stdc++.h> using namespace std; int main() { vector<int> a; int x; // 读入所有导弹高度，输入以 EOF 结束 while (cin >> x) { a.push_back(x); } int n = (int)a.size(); // 第一问：最长不上升子序列长度 // d[k] 表示长度为 k+1 的不上升子序列中，结尾的最大值 vector<int> d1; for (int i = 0; i < n; i++) { int pos = upper_bound(d1.begin(), d1.end(), a[i], greater<int>()) - d1.begin(); if (pos == (int)d1.size()) { d1.push_back(a[i]); } else { d1[pos] = a[i]; } } cout << "第一问答案（一套系统最多拦截）: " << d1.size() << "\n"; // 第二问：最小系统数，即最长严格上升子序列长度 // d2[k] 表示长度为 k+1 的严格上升子序列中，结尾的最小值 vector<int> d2; for (int i = 0; i < n; i++) { int pos = lower_bound(d2.begin(), d2.end(), a[i]) - d2.begin(); if (pos == (int)d2.size()) { d2.push_back(a[i]); } else { d2[pos] = a[i]; } } cout << "第二问答案（最少系统数）: " << d2.size() << "\n"; return 0; }

代码里第一问用了upper_bound加greater<int>()，第二问用了lower_bound，这两个选择都有讲究。第一问要找的是“第一个小于当前值的位置”，因为等于可以继续接，所以必须跳过所有相等元素，upper_bound配合降序比较正好做到这一点。第二问要找“第一个大于等于当前值的位置”，lower_bound天生就是这个语义，因为严格上升不允许相等。

4.2 Python 代码：手写二分更保险

Python 的bisect库配合降序数组需要自定义 key，很多版本支持不好，所以我一般直接手写二分。同时也方便你理解边界到底卡在哪。

import bisect # 第一问：最长不上升子序列长度 def first_question(a): d = [] # d[k] 表示长度为 k+1 的不上升子序列中，结尾的最大值 for x in a: # 找第一个 < x 的位置，因为等于的可以继续接 lo, hi = 0, len(d) while lo < hi: mid = (lo + hi) // 2 if d[mid] < x: hi = mid else: lo = mid + 1 if lo == len(d): d.append(x) else: d[lo] = x return len(d) # 第二问：最长严格上升子序列长度（最少系统数） def second_question(a): d = [] # d[k] 表示长度为 k+1 的严格上升子序列中，结尾的最小值 for x in a: pos = bisect.bisect_left(d, x) if pos == len(d): d.append(x) else: d[pos] = x return len(d) a = [389, 207, 155, 300, 299, 170, 158, 65] print("第一问答案:", first_question(a)) # 6 print("第二问答案:", second_question(a)) # 2

运行结果和之前手动推演完全一致。第一问输出 6，第二问输出 2。

插一句工程习惯：每次提交或者上线这类算法模块之前，最好用一组手工算好的数据跑一遍。我最常干的事就是拿样例数据先手推一遍，再和程序输出对比。这个习惯帮我抓出过无数次边界错误。

4.3 更多测试用例验证

只靠一组数据不够，我再用几组典型场景验证，同时也帮你看清楚边界条件的行为。

第一行和第二行能清楚看到两个问题在等号处理上的差异：全是 5 时，不上升子序列长度是 3，但系统数只需要 1；全是递增时，不上升子序列长度是 1，但系统数需要 5。两个答案并不相等，这正是这道题容易让人迷惑的地方。

5. 实战中常见的坑与排查心得

5.1 等号问题：半小时Debug最常见的元凶

第一问的“不上升”允许相等；第二问的贪心查找中，如果写成“大于”而不含等号，也会出问题。很多初学者觉得自己思路懂了，一写代码就在等号上栽跟头。C++ 里把第一问写成lower_bound(d1.begin(), d1.end(), a[i], greater<int>())，遇到相等元素时会找错位置，最终答案变短。

记住一个口诀：不上升找upper_bound，上升找lower_bound。前者跳过相等，后者不跳过相等。第二问如果误写成upper_bound，遇到重复高度会错误地增加系统数，输出偏大。

5.2 二分边界为什么容易写错

手写二分时，最容易犯的是死循环和越界。标准写法里lo = 0, hi = len(d)，循环条件是lo < hi，mid = (lo + hi) // 2。关键在于当lo = mid + 1还是hi = mid，这取决于你找的是“第一个满足条件”还是“第一个不满足条件”的位置。懒得每次推的话，直接用标准库函数更省心。

但即使是标准库，也要仔细阅读文档确认行为。C++ 的upper_bound在降序比较器下，返回的是第一个“不满足比较条件”的位置，这里的“不满足比较条件”在greater<int>()下就是“第一个小于当前值”的位置。这个弯绕起来很晕，我建议你拿简单数组实际打 log 输出中间过程，一遍就看懂。

5.3 输入数据可能有多行

这类题在竞赛平台里常见输入格式是：第一行一个整数 n，第二行 n 个整数；但有些版本直接给一行，甚至多行直到 EOF。所以我上面的代码用while (cin >> x)直接读到文件末尾，天然兼容两种格式。如果你用for循环读固定数量，先看清题目给的是几个数。

另外，n 可能为 0。虽然导弹数为 0 有点奇怪，但防御性编程建议特判一下，避免第二问输出 0 或者数组越界之类的问题。

5.4 两个问题可以合并成一个模型

第二问“最少系统数”本质上就是另一个方向的“最长严格上升子序列”，两者共享一套二分框架。遇到类似变体时，我一般会先判断：题目问的是“序列内的极限能力”还是“外部资源的最小数量”？前者大概率是 DP，后者大概率是贪心。但最终代码结构完全一样，只是比较符号翻转一下。

6. 扩展思考：这套模型还能用在哪些地方

导弹打飞机是个军事化的包装，剥掉外壳之后，这套贪心算法在任务调度和资源分配里有非常实际的应用。

举个例子，服务器任务调度：一批任务按到达时间排列，每个任务有不同优先级数值，同一个 worker 只能连续处理优先级不高于上一个任务的作业。问最少需要几个 worker。这就是“最少系统数”的完全同构问题。

再举个例子，货物装箱或货车配载：一车货物要求按重量降序装载，一批货物依次到达，问最少需要多少辆车。后面的货物能否装进前面的车，取决于当前车剩余承重是否足够，这跟“系统最后高度是否大于等于当前导弹高度”是同一套判断逻辑。

还有经典会议室安排问题变体：会议要按开始时间递增使用会议室，每个会议室同一时间只能开一个会，问最少需要多少个会议室。剥掉条件包装，也是这个贪心的核心逻辑。

我自己在平时做调度方案的时候，遇到“序列内不能回退”的资源分配问题，第一反应就是套这套贪心+二分的框架。它 O(n log n) 的复杂度在数据量很大时依然能跑得很好，而且代码量少，逻辑不容易出 bug。

另外补充一个进阶联想：如果把“不上升”改成“不下降”，即允许反弹不允许下降，那代码里所有比较符号全部反过来，原理完全一样。这种镜像变换能帮你把一套思路吃透一类题。

最后分享一个我实测下来的小技巧：遇到这种导出式题，先用纸笔把样例走一遍，再把你的输出和标准样例对一遍，通常能省下大量调试时间。刷题不是比谁写得快，而是比谁能一次写对。