B1229 拦截导弹的系统数量求解
B1229 拦截导弹的系统数量求解
【算法标签】 贪心
【语法标签】 :cin/cout、for循环、数组、multiset、lower_bound
某拦截系统的特点:第一发炮弹可打到任意高度,之后每一发都不能高于前一发。
输入:第一行一个整数 (),第二行 个整数表示依次飞来的导弹高度()。计算拦截所有导弹最少需要的系统数。
- 时间限制:1000ms
- 内存限制:16MB
样例输入:
8
389 207 175 300 299 170 158 165样例输出:
2样例解释:系统 1 拦截 (共 5 枚);系统 2 拦截 (共 3 枚)。
本题和「1310 拦截导弹问题」几乎相同,区别仅在于输入格式——本题第一行给出了 ,不需要用
while (cin >> h)判断输入结束。
二、解题思路
为什么又是贪心?
和前面 1310 题一样的逻辑:
- 每来一枚导弹,在现有的拦截系统中,找一个 高度 该导弹且高度最小 的系统来拦截
- 找不到就新开一套
这个策略背后的直觉是保留弹性:用"刚好够"的系统处理当前导弹,把更强的系统留给将来更高的导弹。
两种实现方案
本题 ,朴素 完全可行。但为了拓宽思路,这里同时介绍两种写法:
| 方案 | 时间复杂度 | 核心工具 | 适用场景 |
|---|---|---|---|
| 朴素贪心 | 数组 sys[] + 遍历 | ,思路直观 | |
| 进阶贪心 | multiset + lower_bound | 更大,代码更短 |
方案一:朴素遍历(与 1310 一致)
直接用数组 sys[] 存每套系统的当前拦截高度,对每枚导弹遍历所有系统找最佳适配。
方案二:multiset 二分查找
multiset 是 C++ STL 中的有序多重集合,内部自动保持元素升序排列。关键操作:
s.insert(x)— 插入元素 ,s.lower_bound(x)— 返回第一个 的元素的迭代器,s.erase(it)— 删除迭代器指向的元素,(配合lower_bound使用)
算法流程:
- 初始化空的
multiset<int> s,表示所有系统的当前拦截高度 - 逐个读入导弹高度 :
auto it = s.lower_bound(h):在 中二分查找第一个 的系统- 若
it == s.end():说明没有系统能拦截 ,s.insert(h)(新增一套系统) - 否则:
s.erase(it)删除旧高度,s.insert(h)插入新高度(该系统拦截后高度降为 )
- 最后
s.size()就是最少系统数
手动模拟(方案二,样例数据)
导弹序列:389, 207, 175, 300, 299, 170, 158, 165
| 步骤 | multiset | lower_bound(h) | 结果 | 操作后 | |
|---|---|---|---|---|---|
| 1 | 389 | {} | end()(空集) | 新增 | {389} |
| 2 | 207 | {389} | 指向 389 | 拦截 | {207} |
| 3 | 175 | {207} | 指向 207 | 拦截 | {175} |
| 4 | 300 | {175} | end()(175<300) | 新增 | {175, 300} |
| 5 | 299 | {175, 300} | 指向 300 | 拦截 | {175, 299} |
| 6 | 170 | {175, 299} | 指向 175 | 拦截 | {170, 299} |
| 7 | 158 | {170, 299} | 指向 170 | 拦截 | {158, 299} |
| 8 | 165 | {158, 299} | 指向 299 | 拦截 | {158, 165} |
最终 中有 2 个元素,答案为 2。与手工分配完全一致。
为什么
lower_bound(158)指向 170 而不是 299? 因为 170 是第一个 的元素,multiset 内部升序排列 ,注意这里 158 是之后插入的,实际上 在步骤 7 开始时是 ,lower_bound(158)返回指向 170 的迭代器。
三、参考代码
方案一:朴素 (推荐新手)
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int sys[N]; // 每套系统当前的拦截高度上限
int cnt; // 已有系统数量
int main() {
int n, h;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> h;
// 在所有系统中找"高度≥h 且最小"的
int best = -1;
for (int j = 1; j <= cnt; j++) {
if (sys[j] >= h) {
if (best == -1 || sys[j] < sys[best]) {
best = j;
}
}
}
if (best == -1) {
cnt++;
sys[cnt] = h;
} else {
sys[best] = h;
}
}
cout << cnt << endl;
return 0;
}方案二:进阶 (使用 multiset)
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, h;
cin >> n;
multiset<int> s; // 维护所有系统的当前拦截高度(自动升序)
for (int i = 1; i <= n; i++) {
cin >> h;
// lower_bound: 二分查找第一个 ≥h 的系统
auto it = s.lower_bound(h);
if (it == s.end()) {
// 没有系统能拦截,新增一套
s.insert(h);
} else {
// 找到了最佳适配系统:删旧高度,插新高度
s.erase(it);
s.insert(h);
}
}
// multiset 中元素的个数就是系统套数
cout << s.size() << endl;
return 0;
}易错提醒:
s.erase(h)会删除 multiset 中所有值为 的元素!这里必须用s.erase(it)(迭代器版本),只删除lower_bound找到的那一个元素。
四、复杂度分析
| 方案 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 朴素 | ,每枚导弹遍历所有系统 | ,sys 数组 |
| 进阶 | ,每枚导弹一次 lower_bound + 一次 insert | ,multiset 存储 |
在本题 的限制下,两种方案都能轻松通过。但如果数据规模扩大到 ,方案二仍能高效运行,而方案一会超时。
拓展知识:multiset 的 lower_bound
multiset 和 set 的成员函数 lower_bound(x) 比通用 std::lower_bound 性能更好。原因是:
- 成员函数
s.lower_bound(x)利用了红黑树的内部结构进行二分,复杂度 - 通用函数
std::lower_bound(s.begin(), s.end(), x)无法利用树结构,只能线性扫描,复杂度
因此,在对 set/multiset 做二分查找时,务必使用成员函数。
五、两题对比总结
| 对比项 | 1310 拦截导弹问题 | B1229 拦截导弹的系统数量求解 |
|---|---|---|
| 输入格式 | 一行 个整数,无前置 | 第一行给 ,第二行给数据 |
| 读入方式 | while (cin >> h) | cin >> n; + for 循环 |
| 核心算法 | 贪心:最佳适配() | 贪心:最佳适配( 或 ) |
| 适合学生 | 刚学贪心,练数组遍历 | 学完贪心后,引入 STL 优化 |
掌握了这两道题,就掌握了"导弹拦截"这一类贪心问题的标准解法。同类题目还有洛谷 P1020(最长不上升子序列角度)、Codeforces 上的类似拦截问题等。
