蓝桥杯算法训练VIP-拦截导弹 （C++代码）

解题思路:





注意事项:





参考代码:

#include<cstdio>
#include<cstring>
int a[100005],d[100005],n;
int lis1()
{
    int l,r=n,mid,cnt=0,ans;
    d[++cnt]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]<=d[cnt]) d[++cnt]=a[i];
        else
        {
            l=1;
            r=cnt;
            while(l<=r)
            {
                mid=(l+r)>>1;
                if(d[mid]<a[i])
                {
                    ans=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            d[ans]=a[i];
        }
    }
    return cnt;
}

int lis2()
{
    memset(d,0,sizeof(d));
    int l,r=n,mid,cnt=0,ans;
    d[++cnt]=a[1];
    for(int i=2;i<=n;i++)
    {
        if(a[i]>d[cnt]) d[++cnt]=a[i];
        else
        {
            l=1;
            r=cnt;
            while(l<=r)
            {
                mid=(l+r)>>1;
                if(d[mid]>=a[i])
                {
                    ans=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            d[ans]=a[i];
        }
    }
    return cnt;
}

int main()
{
    int ans;
    while(scanf("%d",&a[++n])==1);
    n-=1;
    printf("%d\n%d",lis1(),lis2());
}