拦截导弹
题目 拦截导弹
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
输入格式
共一行，输入导弹依次飞来的高度。
输出格式
第一行包含一个整数，表示最多能拦截的导弹数。
第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。
数据范围
雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。
输入样例：
389 207 155 300 299 170 158 65
输出样例：
6 2
思路分析
题意分析一下大概就是问 输入的数据 有多少组下降子序列 然后最长下降子序列的长度是多少（严谨一点应该是不上升 可以持平）
1、该数组的最长不上升子序列
2、该数组最少能被几个最长不上升子序列全部覆盖
第二个问题的证明：
要求我们用最少的最长下降子序列对原数组进行全覆盖
考虑一种贪心方案： 对于第i个数来说，把它加入前 i - 1 个数构成的下降子序列组中，所有结尾元素大于第i个数的数中最小的那个数
证明：（最优解 = 贪心解）
假设存在一个最优解，他在考虑第 i 个数放入的下降子序列组中，选择了贪心解方案的后面的一个位置
具体如图所示：（绿色部分，更新了q[i+1]后为保证递增顺序，交换了q[i]和q[i+1]，这一步省略了）
可以观察到，该最优策略使得当前局面差于贪心策略，即能接在(q[i],q[i+1])范围的子序列少了一个
即贪心解 ≤最优解
同理可证，最优策略在考虑第 i 个数放入的下降子序列组中，选择了贪心解方案的后面的第 k个位置也有结论贪心解 ≤最优解
此外，由于贪心解是合法解，所以必然 贪心解 ≥最优解
于是有 贪心解 =最优解
证明：（调整法）
假设存在一种最优策略，不是按照贪心方案进行阶段决策的
则我们可以通过有限次的调整，把最优解调整成贪心解的方案，具体如下图所示
于是，由该决策包容性，得出最优解可以是贪心解。
基本思想是尝试将每个来袭的导弹高度放入已有的系统中，如果当前导弹高度不能放入任何一个系统（即当前导弹的高度大于所有系统的当前可接受的最大高度），则需要增加一个新的系统。维护一个数组q记录每个系统可以接受的最大高度，对于每个导弹，使用二分查找在q中找到可以放入的位置，并更新该系统的可接受的最大高度。如果找不到合适的系统，则开启一个新的系统。最终q的长度（即cnt的值）即为所需的最小系统数。
从前往后做一遍最长下降子序列，同时维护一个数组长度为cnt的单调不减数组q[N] 数组 q[N] 中每个元素维护的是当前以 q[i] 结尾的下降子序列
于是，对于第 i 个元素来说，他能插入的到 q[N] 中的哪个下降子序列中，是存在一个二分性质的
由于要求的是下降子序列且 q[N] 是单调不减的
因此对于所有的 w[i] ，必然存在一个边界 j ，满足∀k∈[0,j),有q[k]<w[i]且 ∀k∈[j,cnt],有w[i]≤q[k] 于是我们就可以用二分来优化找满足性质：w[i]≥q[k]的区间左端点即可
这个写法还是有点一知半解 感觉有道理 类似于单调栈的优化那里 维护多个单调序列 在外面二分 找到可插入的序列 如果都不行 就只能再开一个
我的想法是 能不能做多次呢 第一轮对原序列做最长不下降子序列 然后把那些被找过的都删掉 第二次再对剩下的做最长不下降子序列 重复操作 最后只要看要做几次 就是几个系统？类似于模拟了属于是
实现是可以实现 但是因为没买提高课 进不去题目 不知道是否会超时
回过头来解释一下这个问题
首先是正常的找最长不下降子序列的长度 这个没什么问题
主要是在于 如何找出最少用多少个单调子序列填满数组
——每一个单调子序列都可以看作是一个单调递增的单调栈 判断某个元素能否进入某个单调递增的单调栈 其实只要看该元素与栈顶元素哪个更大 如果该元素更大 就可以放入该单调栈 这是显而易见的 所以 单调栈不需要完全存储下来 只需要存储栈顶元素即可 另外 贪心体现在 如果能加入最开始的单调栈 就一定会比加入后面的单调栈要好 这样空隙会更小 这个自己在脑子里抽象一下 二分为什么有二段性？ 其实这些单调栈的栈顶元素是有一个递减性质在的 可以想象 如果第二个栈的栈顶元素比第一个栈的栈顶元素大 那么那一定会被我们的贪心策略加入第一个单调栈里面去吧 而不会在第二个单调栈 所以 后面的栈顶一定比前面的栈顶要小 所以呈现单减性质 所以具有二段性可以进行二分 如果某个元素比所有的已知栈顶小 就需要开一个新栈
大概长这个样子
代码实现
#include<bits/stdc++.h>
using namespace std;
const int N = 1010, INF = 30010;
int n, x;
int w[N], f[N]; // w数组存储导弹高度，f数组用于DP求最长不下降子序列
int q[N], cnt; // q数组存储每个系统可以接受的最大高度，cnt记录系统数量
int main()
{
while(cin>>x)
w[++n] = x; // 输入导弹高度
// 第一问：计算最多能拦截的导弹数
int res = 0;
for(int i=1;i<=n;i++)
{
f[i]=1; // 初始化当前导弹的最长不下降子序列长度为1
for(int j=0;j<i;j++)
{
if(w[j]>=w[i]) // 如果前面的导弹高度不低于当前导弹
f[i]=max(f[i], f[j]+1); // 更新最长不下降子序列长度
}
res = max(res, f[i]); // 更新全局最大值
}
cout << res << endl;
// 第二问：计算拦截所有导弹最少需要配备的系统数
for(int i = 1;i <= n;i++)
{
int l=0, r=cnt; // 二分查找的范围
while (l < r)
{
int mid =l+r>>1;
if(q[mid]>=w[i])
r = mid; // 找到一个系统，其可以接受的最大高度大于等于当前导弹高度
else
l = mid + 1;
}
// 说明找到的q[r]仍然小于w[i]，即当前导弹高度大于所有系统的当前可接受的最大高度
if (q[r] < w[i])
r ++ ; // 需要增加一个新系统
cnt = max(cnt, r); // 更新系统数量
q[r] = w[i]; // 更新该系统可接受的最大高度为当前导弹高度
}
cout << cnt << endl; // 输出最少需要的系统数
return 0;
}
#include<bits/stdc++.h>
using namespace std;
int maxIntercepts = 0; // 全局变量，记录单次操作中最多能拦截的导弹数
// 函数：拦截导弹并更新剩余导弹序列
void intercept(vector<int>& missiles) {
if (missiles.empty())
return;
vector<int> dp(missiles.size(), 1); // dp[i] 表示以 missiles[i] 结尾的最长不上升子序列的长度
for (int i = 0; i < missiles.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (missiles[i] <= missiles[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
maxIntercepts = max(maxIntercepts, dp[i]); // 更新在所有拦截操作中最多能拦截的导弹数
}
// 识别并移除这一轮中拦截的导弹
vector<int> nextRound;
vector<bool> toRemove(missiles.size(), false);
int maxLength = *max_element(dp.begin(), dp.end());//找出给定范围内（这里是dp向量的全部元素）的最大元素的值
int removeCount = maxLength;
for (int i = missiles.size() - 1; i >= 0 && removeCount > 0; --i) {
if (dp[i] == removeCount) {
toRemove[i] = true; // 标记此导弹被拦截
--removeCount;
}
}
// 构建下一轮剩余的导弹序列
for (int i = 0; i < missiles.size(); ++i) {
if (!toRemove[i])
nextRound.push_back(missiles[i]);
}
missiles = nextRound; // 更新为下一轮的导弹序列
}
int main() {
vector<int> missiles;
int height;
// 输入导弹高度序列
while (cin >> height) {
missiles.push_back(height);
}
int systemsNeeded = 0; // 记录需要的系统数
// 循环，直到所有导弹都被拦截
while (!missiles.empty()) {
intercept(missiles); // 执行拦截操作，并更新剩余导弹序列
++systemsNeeded; // 每进行一次拦截操作，需要的系统数加1
}
// 输出结果
cout << maxIntercepts << endl; // 最多能拦截的导弹数
cout << systemsNeeded << endl; // 最少需要的系统数
return 0;
}
💬 评论