某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。 输入输出格式 输入格式 一行,一个正整数数列,依次表示飞来导弹的高度(雷达给出的高度数据是不大于30000的正整数,导弹数不超过1000) 输出格式 计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统
时间: 2024-04-02 19:32:30 浏览: 167
一种敏捷导弹控制系统的设计方法_李友年
好的,以下是 C++ 代码实现:
```cpp
#include <iostream>
#include <vector>
#include <set>
using namespace std;
// 第一问
int max_interception(vector<int>& nums) {
vector<int> heights;
for (int num : nums) {
if (heights.empty() || num <= heights.back()) {
heights.push_back(num);
} else {
int i = 0;
while (i < heights.size() && heights[i] < num) {
i++;
}
if (i < heights.size()) {
heights[i] = num;
} else {
heights.push_back(num);
}
}
}
return heights.size();
}
// 第二问
int min_systems(vector<int>& nums) {
set<int> systems;
for (int num : nums) {
if (systems.empty()) {
systems.insert(1);
continue;
}
bool added = false;
for (int sys : systems) {
if (num <= sys) {
systems.erase(sys);
systems.insert(num);
added = true;
break;
}
}
if (!added) {
systems.insert(num);
}
}
return systems.size();
}
// 主函数
int main() {
int num;
vector<int> nums;
while (cin >> num) {
nums.push_back(num);
}
cout << max_interception(nums) << endl; // 输出:能够拦截的最多导弹数
cout << min_systems(nums) << endl; // 输出:最少需要几套导弹拦截系统
return 0;
}
```
其中,输入的导弹高度数据可以使用 `while(cin >> num)` 来读取,直到读到文件结束符为止。
阅读全文