又见拦截导弹
时间限制:3000 ms | 内存限制:65535 KB
难度:3
- 描述
-
大家对拦截导弹那个题目应该比较熟悉了,我再叙述一下题意:某国为了防御敌国的导弹袭击,新研制出来一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能超过前一发的高度。突然有一天,雷达捕捉到敌国的导弹来袭。由于该系统存在缺陷,所以如果想把所有的导弹都拦截下来,就要多准备几套这样的导弹拦截系统。但是由于该系统成本太高,所以为了降低成本,请你计算一下最少需要多少套拦截系统。
- 输入
- 有多组测试数据。
每组数据先输入一个整数N(N≤3000),代表有N发导弹来袭。接下来有N个数,分别代表依次飞来的导弹的导弹的高度。当N=-1时表示输入结束。 - 输出
- 每组输出数据占一行,表示最少需要多少套拦截系统。
- 样例输入
-
8 389 207 155 300 299 170 158 65 5 265 156 123 76 26
- 样例输出
-
2 1
感觉这个题就是像是在考栈与DP(说的是最长子序列)。。每个栈都储存着打掉的导弹的高度。。每次一个导弹高度,我们都是在所有栈的栈顶选择一个最接近此导弹高度的,然后让此导弹高度进入到这个栈中。
而nlogn的思想感觉和这个一样的。
ans数组存的就是每个栈顶元素。而求下界也就是最接近此导弹高度的。而求下界你使用了二分查找的方法(没有使用顺序查找,当然此题二分与顺序查找只差了4ms。。但是数据要是更大感觉二分的高效就更明显了。)。当然可以证明ans数组是有序的。(当时这样想时我还以为,这应该是无序的,后来用笔画了下,问题是递推的,后面的一定比前面大。要。反证法即可)
由于本人没有看DP。。对DP算法一点也不懂。准备近期深入。
#include<iostream> #include<cstdio> #include<cstdlib> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<set> #include<map> #include<string> #include<cstring> #include<cmath> using namespace std; /**************************** By:七柳先森丶 Date: 12.22 2014 *****************************/ //利用数组模拟。mn数组中保留的是每个系统中最后一次发射的高度且是最优的。。
//方法1:顺序查找。二分算法待更新。
const int mx=3001; int mn[mx],a[mx]; int main() { int n,ans; while(scanf("%d",&n)){ if(n==-1) break; ans=0; for(int i=0;i<n;i++) scanf("%d",&a[i]); mn[ans]=a[0]; int j; for(int i=1;i<n;i++){ for( j=0;j<=ans;j++){ if(a[i]<=mn[j]){ //此时可以证明顺序选择是最优的选择方案。 mn[j]=a[i]; break; } } //当前没有合适的系统。新增。 if(j == (ans+1)){ mn[ans+1]=a[i]; ans++; } } printf("%d\n",ans+1); } return 0; }