1310 拦截导弹问题
1310 拦截导弹问题
【算法标签】 贪心
【语法标签】 :数组、for循环、while循环(cin读入)
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。这种拦截系统有一个特点:第一发炮弹可以打到任意高度,但之后的每一发炮弹都不能高于前一发的高度。
现在雷达探测到敌国的 枚导弹依次飞来(,高度 ),输入为一行 个整数(没有单独给出 ),表示依次飞来的导弹高度。你的任务是计算:要拦截所有导弹,最少需要配备多少套这种拦截系统。
样例输入:
389 207 155 300 299 170 158 65样例输出:
2样例解释:系统 1 拦截 ,系统 2 拦截 ,两套系统即可覆盖全部 8 枚导弹。
注意:本题输入格式特殊——没有先给出 ,而是直接给出一行整数。代码中需要用
while (cin >> h)的方式读入所有数据,直到输入结束。
二、解题思路
数据规模分析
- 导弹数量 ,高度
- 的算法在最坏情况下执行约 次操作,可以轻松通过
贪心策略:最佳适配
想象你是一名指挥官,手里有若干套拦截系统。每当雷达报告一枚新的导弹高度 ,你需要决定用哪套系统去拦截。
贪心选择:在所有能够拦截该导弹的系统(即系统当前拦截高度 )中,选择拦截高度最小的那一套。
为什么选最小的,不选最大的?
- 如果用高度大的系统去打一枚"矮"导弹,那套系统之后的拦截能力会大幅下降(从高变矮)。
- 而用高度最小的系统去打,保留了高度大的系统去应对将来可能出现的"高"导弹。
- 这就像分配任务——把轻松的任务交给能力刚好够的人,把强者留给困难的任务。
算法流程
- 维护一个数组
sys[1..cnt],sys[i]表示第 套系统当前能拦截的最高高度(即该系统上一次拦截的导弹高度) - 逐个读入导弹高度 :
- 遍历所有已有系统,找到 高度 且高度最小 的系统编号
best - 找到了:让该系统拦截,更新
sys[best] = h(拦截后该系统的新"天花板"变为 ) - 没找到:新增一套系统,
cnt++,sys[cnt] = h
- 遍历所有已有系统,找到 高度 且高度最小 的系统编号
- 输出
cnt
手动模拟样例
以样例 [389, 207, 155, 300, 299, 170, 158, 65] 逐步演示:
| 步骤 | 导弹 | 当前系统状态 | 查找过程 | 操作 | 操作后状态 |
|---|---|---|---|---|---|
| 1 | 389 | (空) | 无系统,无法拦截 | 新增系统1 | sys[1]=389 |
| 2 | 207 | sys[1]=389 | 389 207,唯一选择 | 系统1拦截 | sys[1]=207 |
| 3 | 155 | sys[1]=207 | 207 155,唯一选择 | 系统1拦截 | sys[1]=155 |
| 4 | 300 | sys[1]=155 | 155 300,无法拦截 | 新增系统2 | sys[1]=155, sys[2]=300 |
| 5 | 299 | sys[1]=155 299,sys[2]=300 299 | 系统2可拦截,唯一 | 系统2拦截 | sys[1]=155, sys[2]=299 |
| 6 | 170 | sys[1]=155 170,sys[2]=299 170 | 系统2可拦截,唯一 | 系统2拦截 | sys[1]=155, sys[2]=170 |
| 7 | 158 | sys[1]=155 158,sys[2]=170 158 | 系统2可拦截,唯一 | 系统2拦截 | sys[1]=155, sys[2]=158 |
| 8 | 65 | sys[1]=155 65,sys[2]=158 65 | 两套都可,155 更小 | 系统1拦截 | sys[1]=65, sys[2]=158 |
最终结果:2 套系统。系统1最终高度 65(拦截了第1,2,3,8枚),系统2最终高度 158(拦截了第4,5,6,7枚)。
思考:为什么贪心是正确的?
假设存在一个最优解,我们要证明"最佳适配"贪心策略不会比它差。
关键观察:每套系统的拦截高度序列是单调递减的。当我们用"高度最小且够用"的系统去拦截当前导弹时,我们留给未来的"剩余拦截能力"是最大的——因为那些高度更大的系统被保留了下来。这是一个经典的"保留弹性"贪心思想,类似于区间调度问题中的"最早结束优先"。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1005; // n ≤ 1000,多开一点
int sys[N]; // sys[i]:第 i 套系统当前的拦截高度上限
int cnt; // 当前系统数量
int main() {
int h;
// 逐枚读入导弹高度(输入为一行若干整数,无前置 n)
while (cin >> h) {
// 在所有已有系统中找"最佳适配"
int best = -1; // best = -1 表示还没找到
for (int i = 1; i <= cnt; i++) {
if (sys[i] >= h) { // 系统 i 能拦截这枚导弹
if (best == -1 || sys[i] < sys[best]) {
best = i; // 选拦截高度最小的
}
}
}
if (best == -1) {
// 没有系统能拦截,新增一套
cnt++;
sys[cnt] = h;
} else {
// 用 best 系统拦截,更新其高度上限
sys[best] = h;
}
}
cout << cnt << endl;
return 0;
}四、复杂度分析
- 时间复杂度:,其中 为导弹数量。每枚导弹都要遍历一遍已有系统,最坏情况下(导弹高度严格递增,每枚都需要新建系统)遍历 次。当 时约 次,完全可以接受。
- 空间复杂度:,即
sys数组的大小。
扩展思考
如果 更大(比如 ), 会超时。此时可以用 multiset(有序多重集合)维护系统高度,每次用 lower_bound 二分查找,将复杂度优化到 。初学者先掌握基础版本即可,进阶版见下一题 B1229。
