拦截导弹，贪心+二分的nlogn做法

解题思路:

lower_bound( )和upper_bound( )都是利用二分查找的方法在一个排好序的数组中进行查找的。

1、在从小到大的排序数组中，

lower_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num)：从数组的begin位置到end-1位置二分查找第一个大于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

2、在从大到小的排序数组中，重载lower_bound()和upper_bound()

lower_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于或等于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

upper_bound( begin,end,num,greater<type>() ):从数组的begin位置到end-1位置二分查找第一个小于num的数字，找到返回该数字的地址，不存在则返回end。通过返回的地址减去起始地址begin,得到找到数字在数组中的下标。

注意事项:

参考代码:

#include <iostream>
#include <algorithm>
using namespace std;

int n = 1, a[100005], nup[100005], up[100005], len = 1, cnt = 1;

bool cmp(int x, int y)
{
	return x > y;
}

int main()
{
	while (cin >> a[n]) n++;
	nup[1] = up[1] = a[1];
	for (int i = 2; i < n; ++i) {
		if (nup[len] >= a[i]) nup[++len] = a[i];
		else nup[upper_bound(nup + 1, nup + len + 1, a[i], cmp) - nup] = a[i];
		if (up[cnt] < a[i]) up[++cnt] = a[i];
		else up[lower_bound(up + 1, up + cnt + 1, a[i]) - up] = a[i];
	}
	cout << len << endl << cnt << endl;
	return 0;
}