【例9.4】拦截导弹(Noip1999)

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int a[N], d[N], len, h, n;
int main()
{
	while(cin >> h)
		a[++n] = h;
	d[++len] = a[1];
	for(int i = 2; i <= n; ++i)
	{
	    if(a[i] <= d[len])
            d[++len] = a[i];
	    else
	    {
	        int l = 1, r = len, m;
	        while(l < r)
	        {
	            m = (l+r)/2;
	            if(d[m] < a[i])
	               r = m;
	            else
	               l = m+1;
            }
            d[l] = a[i];
        }
    }
    cout << len << endl;
    len = 0;
    d[++len] = a[1];
	for(int i = 2; i <= n; ++i)
	{
	    if(a[i] > d[len])
	        d[++len] = a[i];
	    else
	    {
            int l = 1, r = len, m;
            while(l < r)
            {
                m = (l+r)/2;
                if(d[m] >= a[i])
                    r = m;
                else
                    l = m+1;
            }
            d[l] = a[i];
        }
	}
	cout << len << endl;
	return 0;
}