【题目描述】
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。
某天,雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度数据是不大于$30000$的正整数,导弹数不超过$1000$),计算这套系统最多能拦截多少导弹,如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
【输入格式】
共一行,输入导弹依次飞来的高度。
【输出格式】
第一行包含一个整数,表示最多能拦截的导弹数。
第二行包含一个整数,表示要拦截所有导弹最少要配备的系统数。
【数据范围】
雷达给出的高度数据是不大于$30000$的正整数,导弹数不超过$1000$(优化版代码$O(nlogn)$可过数据范围为$100000$)。
【输入样例】
389 207 155 300 299 170 158 65
【输出样例】
6
2
【分析】
计算这套系统最多能拦截多少导弹即为求解最长下降子序列。
对于求解最少要配备多少套这种导弹拦截系统,可使用贪心算法进行分析:
从前往后扫描每个数:
- 情况一:如果现有的子序列的结尾都小于当前数,则创建新子序列
- 情况二:将当前数放到结尾大于等于它的最小的子序列后面
我们用$g[i]$表示第$i$个下降子序列末尾的数,因此$g$一定是单调递增的
优化:
对于求解最长下降子序列问题,可使用贪心与二分的思想将复杂度优化至$O(nlogn)$,对于第二个子问题,根据上述分析,也可使用二分的方法找到结尾大于等于该数的最小的子序列,因此复杂度也为$O(nlogn)$。
【朴素版代码$O(n^2)$】
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int h[N], f[N], g[N];
int n, res, cnt;
int main()
{
while (cin >> h[n]) n++;
for (int i = 0; i < n; i++)
{
f[i] = 1;
for (int j = 0; j < i; j++)
if (h[j] >= h[i]) f[i] = max(f[i], f[j] + 1);
res = max(res, f[i]);
int k = 0;
while (k < cnt && g[k] < h[i]) k++;
g[k] = h[i];
if (k == cnt) cnt++;
}
cout << res << endl << cnt << endl;
return 0;
}
【优化版代码$O(nlogn)$】
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int h[N], f[N], g[N];
int n, res, cnt;
int main()
{
while (cin >> h[n]) n++;
f[res++] = h[0], g[cnt++] = h[0];
for (int i = 1; i < n; i++)
{
if (h[i] <= f[res - 1]) f[res++] = h[i];
else
{
int l = 0, r = res - 1;
while (l < r)
{
int mid = l + r >> 1;
if (f[mid] < h[i]) r = mid;
else l = mid + 1;
}
f[r] = h[i];
}
int l = 0, r = cnt;//可能g中所有数都小于当前数,需要开新序列,因此r需要+1,
while (l < r)//二分找到第一个大于等于当前数的位置
{
int mid = l + r >> 1;
if (g[mid] >= h[i]) r = mid;
else l = mid + 1;
}
g[r] = h[i];
if (r == cnt) cnt++;
}
cout << res << endl << cnt << endl;
return 0;
}
请问第二问的贪心做法中
为什么不是
题目说是不高于,为什么在贪心的时候需要把当前数放到比它大的数后面,而不是大于等于它的数后面
描述有漏洞。但是直击要害,易懂