主要内容 #

1. 问题描述
2. 算法思路
3. 参考程序

1. 问题描述 #

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统，但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度不大于30000的正整数）。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统。
输入格式
n颗依次飞来的高度（1≤n≤1000）。
输出格式
要拦截所有导弹最小配备的系统数k。
输入样例
389 207 155 300 299 170 158 65
输出样例
2

2. 算法思路 #

假设k为当前配备的系统数目。如果导弹i的高度高于所有系统的最低高度，则断定导弹i不能被这些系统所拦截，应该增设一套系统拦截导弹；若导弹i低于某些系统的最低拦截高度，那么导弹i均可被这些系统所拦截。究竟选择哪个系统拦截可使得配备的系统数目最少，需要采用贪心策略，选择其中最低拦截高度最小的一套系统，即导弹i的与系统最低高度最接近的那一套系统。
以此类推，直至分析了n枚导弹的高度为止。此时k即为应配备的最少的系统数。
我们设定一个数组b来保存每套系统当前的最低高度，如b[1]表示的就是第一套系统的最低高度。对于每一个来袭的导弹，我们找到一个最符合条件的（贪心）即可。
那么如何找到呢？
如果a[i]< b[j] （j表示当前判断的是第几套），则这个导弹可以被此套系统拦截，此时又分两种情况：
当前来袭还没分配，分配给这一套系统，p=j;
已经分配了给某系统，判断哪个更小，如1系统500，2系统400，此时来袭导弹高度390，那么我们肯定要分配给400那套系统去拦截。

3. 参考代码 #

#include<iostream>
#include<string.h>
using namespace std;
int main()
{
    int a[1001];
    int b[1001];
    int k,n,p;
    cin>>n;
    for(int i=1;i<=n;i++){//输入
        cin>>a[i];
    }
    b[1]=a[1];//初始化，第一个导弹放第一组
    k=1;//初始化，一套导弹系统
    for(int i=2;i<=n;i++){
        p=0;
        for(int j=1;j<=k;j++){//看能不能使用已有的导弹系统
            if(b[j]>a[i]){//这套系统大于a[i]的a高度
                if(p==0) p=j;//p还没有指定
                else if(b[j]<b[p]) p=j;
            }
        }
        if(p==0){//没找到能用的
            k++;
            b[k]=a[i];
        }else{
            b[k]=a[i];
        }
    }
    cout<<k<<endl;
    return 0;
}