算法随笔：洛谷 P1020 [NOIP 1999 提高组] 导弹拦截

关于STL容器，动态规划里也有很好的使用方式，今天介绍一道导弹拦截的经典题目

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

两行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

说明/提示

对于前 50% 数据，满足导弹的个数不超过

10

4

10^4

104个。该部分数据总分共 100 分。可使用

O

(

N

2

)

O(N^2)

O(N2) 做法通过。 对于后 50% 的数据，满足导弹的个数不超过

10

5

10^5

105个。该部分数据总分也为 100 分。请使用

O

(

N

log

⁡

N

)

O(N \\log N)

O(NlogN) 做法通过。

题目分析

这个问题包含两个子问题：

算法选择

数据范围

N

N

N 最大可达

10

5

10^5

105，因此我们需要

O

(

N

log

⁡

N

)

O(N \\log N)

O(NlogN) 的算法。普通的

O

(

N

2

)

O(N^2)

O(N2) 动态规划只能通过前 50% 的数据。（如果不能理解动态可以先去看这道板子题洛谷B3637 最长上升子序列)

我们使用贪心 + 二分查找的方法：

第一问（最长不上升子序列）：

• 维护一个数组 d1，d1[i] 表示长度为 i+1 的不上升子序列的末尾元素的最大值。
• 为了让子序列更长，我们希望末尾元素尽可能大，这样后面能接纳的数就更多。因此 d1 数组是单调递减的。
• 遍历输入的高度 h：
  • 如果 d1 为空或 h 小于等于 d1 的最后一个元素，直接将 h 接在末尾，序列长度加 1。
  • 否则，h 大于 d1 的最后一个元素。利用二分查找（upper_bound 配合 greater），在 d1 中找到第一个小于 h 的数，并用 h 替换它。这样做是为了让该长度的子序列末尾变大，增加潜力。

第二问（最长上升子序列）：

• 维护一个数组 d2，d2[i] 表示长度为 i+1 的上升子序列的末尾元素的最小值。
• 为了让子序列更长，我们希望末尾元素尽可能小。d2 数组是单调递增的。
• 遍历输入的高度 h：
  • 如果 d2 为空或 h 大于 d2 的最后一个元素，直接将 h 接在末尾。
  • 否则，h 小于等于 d2 的最后一个元素。利用二分查找（lower_bound），在 d2 中找到第一个大于等于 h 的数，并用 h 替换它。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
// 优化输入输出效率
ios::sync_with_stdio(false);
cin.tie(0);

vector<int> a;
int h;
// 循环读取输入直到结束
while (cin >> h)
a.push_back(h);

if (a.empty()) {
cout << 0 << endl << 0 << endl;
return 0;
}

// 第一问：最长不上升子序列 (LNIS)
// dp1 存储的是长度为 i+1 的不上升子序列结尾的最大可能值
// 数组保持降序
vector<int> dp1;
for (int x : a) {
// 如果序列为空，或者当前导弹高度 x 小于等于当前序列末尾（符合不上升规则）
if (dp1.empty() || x <= dp1.back()) {
dp1.push_back(x);
} else {
// 如果 x > dp1.back()，说明 x 不能接在最长序列后面
// 但 x 比某些较短序列的结尾要大，用 x 替换掉第一个严格小于 x 的数
// 这样可以保持序列长度不变，但把结尾变得更大（更有利于后续衔接）
// 因为 dp1 是降序的，使用 upper_bound + greater<int> 寻找第一个小于 x 的元素
auto it = upper_bound(dp1.begin(), dp1.end(), x, greater<int>());
*it = x;
}
}
cout << dp1.size() << endl;

// 第二问：最少系统数 = 最长上升子序列 (LIS) 的长度
// dp2 存储的是长度为 i+1 的上升子序列结尾的最小可能值
// 数组保持升序
vector<int> dp2;
for (int x : a) {
// 如果序列为空，或者当前导弹高度 x 大于当前序列末尾（符合上升规则）
if (dp2.empty() || x > dp2.back()) {
dp2.push_back(x);
} else {
// 如果 x <= dp2.back()，说明 x 可以让某个长度的上升序列结尾变得更小
// 寻找第一个大于等于 x 的数并替换它
// 因为 dp2 是升序的，使用 lower_bound
auto it = lower_bound(dp2.begin(), dp2.end(), x);
*it = x;
}
}
cout << dp2.size() << endl;

return 0;
}

复杂度分析

就这样，利用队列的做法，我们的时间复杂度就从

O

(

N

2

)

O(N ^2)

O(N2)到了

O

(

N

log

⁡

N

)

O(N \\log N)

O(NlogN)，这就是一个巨大的提升啊，在算法比赛中，如果你使出这一招，那将是姜味大鸡啊！！！ 特别是acm比赛中，可能就是一题的区别！！！

关于Dilworth 定理

Dilworth 定理的名字听起来很高大上，但其实它的核心思想非常直观，尤其是在结合具体例子（比如这道导弹拦截题）的时候。

我们可以用一句大白话来概括它：

“如果要用最少的『容器』把所有东西装完，那么『容器』的最少数量，就等于那个『最难搞、最不能共存』的集合的大小。”

1. 结合导弹题来理解

在导弹拦截这道题里，我们可以定义两个概念：

• 顺从的关系（链）：指不上升序列（例如 300 -> 200 -> 100）。这代表一套拦截系统可以顺畅地把它们都吃掉。
• 矛盾的关系（反链）：指上升序列（例如 5 -> 10 -> 20）。这代表它们之间是“矛盾”的，任何一套系统吃了 5 就吃不了 10，吃了 10 就吃不了 20。

Dilworth 定理告诉我们： 想要把所有导弹都拦截下来，最少需要的系统数量，等于这堆导弹里最长上升子序列（最严重的矛盾）的长度。

2. 为什么是这样？（通俗推导）

想象一下，如果有 5 枚导弹飞来，高度分别是 10, 20, 30, 40, 50。

• 矛盾点：这是一组完全递增的序列。
• 系统限制：你的系统只能打“越来越低”的，或者“平着”的。
• 推论：
  • 第 1 套系统如果打了 10，它下次只能打 <=10 的，绝对打不到 20。
  • 第 2 套系统如果打了 20，它下次只能打 <=20 的，绝对打不到 30。
  • …
• 结论：因为这 5 个数互斥（互相之间谁也不能接在谁后面），所以你必须拿出 5 套系统，每套系统专门伺候其中一个数。

所以： 只要你能找到一个长度为

K

K

K 的上升子序列（比如长度为 5），这就意味着至少有

K

K

K 个元素是无法共用同一套系统的，因此你至少需要

K

K

K 套系统。

Dilworth 定理进一步证明了：你最少需要的系统数，恰好就等于这个最长的矛盾序列的长度，不多也不少。

3. 生活中的类比：会议室预订

假设你要给公司安排会议室。

• 规则：同一个会议室里的会议时间不能重叠（这叫“一条链”）。
• 情况：如果在 上午 10:00这个时间点，有 5 个会议 同时要开。
• 矛盾：这 5 个会议就是“反链”（互相冲突，谁也没法等谁）。
• 结果：你最少需要配备 5 间会议室。

总结

在导弹拦截这道题的第二问中：

不知道这样解释大家能不能理解，如果你觉得我讲的不错，不妨给我三连吧。

下期预告：《单调队列》高手的秘密武器