信息学奥赛一本通T1322-拦截导弹问题-题解（C/C++语言代码）

解题思路:

注意事项:

参考代码:#include<iostream>
#include<cstring>
#include<cmath>
#define MAXN 1000
using namespace std;
int a[MAXN+10];//导弹飞来时的高度
int l[MAXN+10];//拦截导弹最低高度
int main()
{
    memset(a,0,sizeof(a));
    memset(l,0,sizeof(l));
    int n=1;
    while(cin>>a[n])
    {
        n++;
    }
    int k=1;//拦截导弹系统数
    int p,j=1;
    l[k]=a[1];
    for(int i=2;i<=n;i++)
    {
        p=0;//注意每次循环时需要p=0
        for(int j=1;j<=k;j++)//注意，j<=k
        {
            if(l[j]>=a[i])
            {
                if(p==0) p=j;
                else if(l[p]>l[j]) p=j;
//如果同时满足例如l[1]=155>65,l[2]=158>65,则应该应将最小值赋值给最小拦截系统
            }
        }
        if(p==0)
        {
            k++;//如果发现a[i]>l[j],则应该增加一个系统
            l[k]=a[i];//更新新系统的最小值
        }
        else l[p]=a[i];//更新原系统的拦截最小值
        //maxx=max(maxx,p);
    }
    cout<<k<<endl;
    return 0;
}