广告支持模式的网站百度品牌广告是什么
P1020 [NOIP 1999 提高组] 导弹拦截 - 洛谷
P1020 [NOIP 1999 提高组] 导弹拦截 - 洛谷
题解来自洛谷题解，仅仅用于自己整理知识
这段代码是 NOIP1999 提高组第一题「导弹拦截系统」的一个 高效 O(n log n) 解法，目标是解决两件事：
-
最多能拦截多少导弹（只有一套系统）
→ 即求一个 最长不升子序列（Longest Decreasing Subsequence，LDS） 的长度 -
拦截所有导弹最少需要几套系统
→ 即将整个序列划分成最少数量的 不升子序列
✅ 解题思路概览
这段代码用了经典的 贪心 + 二分 + tail 数组维护方式（也是 LIS 的优化思路，反过来处理即可用于 LDS）。
const int N = 1e7 + 10;
int n, res, a[N], f[N];
-
a[N]：存储导弹高度 -
f[N]：辅助数组，类似于“每种长度的序列的末尾最小值” -
n：导弹总数 -
res：结果值（最长长度）
while(cin >> x) a[++n] = x;
reverse(a + 1, a + n + 1);
为什么要反转 a[1...n]？
因为原题求的是 最长不升子序列（LDS）
而 LIS（最长上升子序列）的经典做法就是用 lower_bound 来查找位置。
把问题反转之后求 LIS，就等价于在原序列上求 LDS。
第一问：最长不升子序列（LDS）长度
memset(f, 0x3f, sizeof(f)); // 初始化 f[] 为无穷大
for(int i = 1; i <= n; i++) {int l = 1, r = i;while(l < r) {int mid = (r + l) / 2;if(f[mid] > a[i]) r = mid;else l = mid + 1;}f[l] = min(f[l], a[i]);res = max(res, l);
}
cout << res << endl;
✅ 说明：
我们想维护一个数组 f[i]：
-
表示长度为
i的不升子序列末尾的最小值
🚀 每次二分查找：
找的是 f[pos] > a[i] 的最小 pos，因为反转后问题就成了找 最长上升子序列
-
如果找到，就替换
f[pos]为更小的值，有利于后续增长 -
如果找不到，就在末尾新增
🔍 解释（二分查找目标）：
寻找最小的下标 l，使得 f[l] > a[i]
换句话说：
-
找到一个位置
l，可以插入a[i]，以维持f[1...l]是严格递减的 -
这是反转过的最长上升子序列的技巧 —— 用
lower_bound思路求 LDS
✅ 为什么这样做？
我们维护 f[] 的单调性，使得：
-
f[i]越小越好 → 更容易接后面的更小值 -
如果
a[i]能接在某个f[l]之后，就更新它（使结尾更优）
f[l] = min(f[l], a[i]);
🔍 解释：
将 a[i] 放入 f[l] 这个位置（更新为较小值）：
-
表示存在一个长度为
l的不升子序列，其结尾为a[i] -
如果原来的
f[l]更大，那现在用更小的a[i]替代它，有利于后续元素加入
第二问：最少系统数（最少不升子序列划分）
memset(f, 0x3f, sizeof(f));
reverse(a + 1, a + n + 1); // 再反回来
res = 0;
for (int i = 1; i <= n; i++) {int l = 1, r = i;while (l < r) {int mid = (l + r) / 2;if (f[mid] >= a[i]) r = mid;else l = mid + 1;}f[l] = min(f[l], a[i]);res = max(res, l);
}
cout << res;
| 问题 | 方法 | 目标 | 二分条件 | 更新策略 |
|---|---|---|---|---|
| 最长不升子序列 | LIS on reversed | 找最长 | f[mid] > a[i] | f[l] = min(f[l], a[i]) |
| 最少系统数量 | 贪心组系统 | 分组 | f[mid] >= a[i] | f[l] = min(f[l], a[i]) |