洛谷 P1020 导弹拦截

阳光穿透心脏的1/2处 2022-05-28 12:15 165阅读 0赞

## 题目描述 ##

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于50000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

## 输入输出格式 ##

输入格式：

一行，若干个整数（个数少于100000）

输出格式：

2行，每行一个整数，第一个数字表示这套系统最多能拦截多少导弹，第二个数字表示如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

## 输入输出样例 ##

输入样例\#1： 复制

389 207 155 300 299 170 158 65

输出样例\#1： 复制

6
    2

## 说明 ##

为了让大家更好地测试n方算法，本题开启spj，n方100分，nlogn200分

每点两问，按问给分

思路：第一问是求最长不上升子序列的长度，第二问是求最长上升子序列的长度。

用队列存储，加上二分即可得到答案

#include<iostream>
    #include<algorithm>
    using namespace std;
    #define Maxn 100002
    
    int X[Maxn];
    int que_non_up[Maxn];
    int que__up[Maxn];
    int len_non_up;//不上升队列的长度
    int len_up;//上升队列的长度
    
    int main()
    {
    	//freopen("1.txt", "r", stdin);
    	int hight;
    	int num = 1;//序列长度
    	while (~scanf("%d", &hight)){X[num++] = hight;}
    	num--;
    
    	//求最长上升子序列
    	que__up[0] = -1;
    	for (int i = 1; i <= num; i++)
    	{
    		if (X[i] > que__up[len_up]){ que__up[++len_up] = X[i];}
    		else
    		{
    			int l = 1, r = len_up;
    			while (l < r)
    			{
    				int mid = (l + r) / 2;
    				if (X[i]>que__up[mid]) l = mid + 1;
    				else r = mid;
    			}
    			que__up[l] = X[i];
    		}
    	}
    	//求最长不上升子序列
    	que_non_up[0] = 50005;
    	for (int i = 1; i <= num; i++)
    	{
    		if (X[i] <= que_non_up[len_non_up]){ que_non_up[++len_non_up] = X[i]; }
    		else
    		{
    			int l = 1, r = len_non_up;
    			while (l < r)
    			{
    				int mid = (r + l) / 2;
    				if (X[i] <= que_non_up[mid])l = mid + 1;
    				else r = mid;
    			}
    			que_non_up[l] = X[i];
    		}
    	}
    	cout << len_non_up << endl << len_up << endl;
    	return 0;
    }