hdu 1257 贪心+二分搜索

Problem: http://acm.hdu.edu.cn/showproblem.php?pid=1257

依次拦截导弹，如果当前存在的拦截系统无法拦截该导弹，增加一个拦截系统

否则将当前拦截系统中不小于该导弹高度的最小高度的拦截系统的高度设置为该导弹的高度

#include<cstdio>
int n,a,lj[10000]={0},ans;
void work(){
    int L=1,R=ans;
    while(L<R){//二分搜索不小于a的最小高度的拦截系统 
        int M=(L+R)/2;
        if(lj[M]<a)L=M+1;
        else R=M;
    }
    lj[L]=a;//更新系统 
}
int main()
{
    while(scanf("%d",&n)!=EOF){
        ans=0;
        for(int i=0;i<n;i++){
            scanf("%d",&a);
            if(a>lj[ans])lj[++ans]=a;//增加一个新的拦截系统 
            else work();
        }
        printf("%d
",ans);
    }
    return 0;
}

View Code

二分搜索，妥妥的速度，妥妥的减少空间浪费...