2019-03-17 拦截导弹（NlogN）

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
const int maxn=100000+1;
int cnt,n,b[maxn],d[maxn],m[maxn];
int main(void)
{
    int x;
    while(cin>>x)
    {
        b[++n]=x;
    }
    int len=0;
    d[++len]=b[1];
    for(int i=2;i<=n;i++)
    {
        if(d[len]>=b[i]) d[++len]=b[i];
        else
        {
            int p=upper_bound(d+1,d+1+len,b[i],greater<int>())-d;
            d[p]=b[i];
        }
    }
    //for(int i=1;i<=n;i++) cout<<len[i]<< " ";
    //cout<<endl;
    m[++cnt]=b[1];
    for(int i=2;i<=n;i++)
    {
        int index=-1,Min=0x7fffffff;
        for(int j=1;j<=cnt;j++)
        {
            if(m[j]>=b[i] && m[j]-b[i]<Min)
            {
                Min=m[j]-b[i];
                index=j;
            }
        }
        if(index==-1) m[++cnt]=b[i];
        else m[index]=b[i];
    }
    cout<<len<<endl;
    cout<<cnt;
    return 0;
}