洛谷P1020 飛彈攔截(求最長上升子序列和最長非上升子序列---二分查找)

題目描述

某國為了防禦敵國的飛彈襲擊，發展出一種飛彈攔截系統。但是這種飛彈攔截系統有一個缺陷：雖然它的第一發炮彈能夠到達任意的高度，但是以後每一發炮彈都不能高于前一發的高度。某天，雷達捕捉到敵國的飛彈來襲。由于該系統還在試用階段，是以隻有一套系統，是以有可能不能攔截所有的飛彈。

輸入飛彈依次飛來的高度（雷達給出的高度資料是≤50000的正整數），計算這套系統最多能攔截多少飛彈，如果要攔截所有飛彈最少要配備多少套這種飛彈攔截系統。

輸入輸出格式

輸入格式：

1行，若幹個整數（個數≤100000）

輸出格式：

2行，每行一個整數，第一個數字表示這套系統最多能攔截多少飛彈，第二個數字表示如果要攔截所有飛彈最少要配備多少套這種飛彈攔截系統。

輸入樣例#1：

389 207 155 300 299 170 158 65

輸出樣例#1：

6

2

思路：

第一個問就是很明顯求最長的非上升子序列的長度，而第二個問題是求最長上升子序列的長度，要用到Dilworth定理，還要一種證明是這麼證明的：

可直接利用STL的庫函數：

lower_bound()和upper_bound()實作二分查找，回憶一下二者的用法：

一、當數組為升序時：

lower_bound( begin,end,num)：從數組的begin位置到end-1位置二分查找第一個大于或等于num的數字，找到傳回該數字的位址，不存在則傳回end。通過傳回的位址減去起始位址begin,得到找到數字在數組中的下标。

upper_bound( begin,end,num)：從數組的begin位置到end-1位置二分查找第一個大于num的數字，找到傳回該數字的位址，不存在則傳回end。通過傳回的位址減去起始位址begin,得到找到數字在數組中的下标。

一、當數組為降序時，需要重載函數：

lower_bound( begin,end,num,greater() )：從數組的begin位置到end-1位置二分查找第一個小于或等于num的數字，找到傳回該數字的位址，不存在則傳回end。通過傳回的位址減去起始位址begin,得到找到數字在數組中的下标。

upper_bound( begin,end,num,greater() ):從數組的begin位置到end-1位置二分查找第一個小于num的數字，找到傳回該數字的位址，不存在則傳回end。通過傳回的位址減去起始位址begin,得到找到數字在數組中的下标。

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<sstream>
using namespace std;

const int maxn = 100000 + 5;

int down[maxn];
int up[maxn];

int main()
{

	
	int num;
	scanf("%d", &num);
	down[1] = up[1] = num;
	int didx = 1;
	int uidx = 1;
	while (~scanf("%d", &num)) {
		if (num > up[uidx])
			up[++uidx] = num;
		else if (num < up[uidx]) {
			int l = 1;
			int r = uidx;
			while (l <= r) {
				int m = l + (r - l) / 2;
				if (up[m] >= num)
					r = m - 1;
				else
					l = m + 1;
			}
			up[l] = num;
			//int p = lower_bound(up+1, up+ uidx+1, num) - up; 從左往右找出第一個大于等于num的數，-up傳回數組下标
			//up[p] = num;
		}

		if (num <= down[didx])
			down[++didx] = num;

		else {
			int l = 1;
			int r = didx;
			while (l <= r) {
				int m = l + (r - l) / 2;
				if (down[m] < num)  //注意這裡不能有等于
					r = m - 1;
				else
					l = m + 1;
			}			
			down[l] = num;
			//int p = upper_bound(down+1, down + didx+1, num, greater<int>()) - down; 從左往右找出第一個大于num的數，-down傳回數組下标
            //down[p] = num;
		}

	}	
	cout << didx << endl << uidx;
			
	return 0;
}