-
题目描述
-
易琢然今天玩使命召唤，被敌军用空对地导弹轰炸，很不爽；众所周知，易琢然很不老实，他开了外挂；外挂第一次可以打掉任意高度的导弹，之后每一次都不能打掉大于上一次高度的导弹；但易琢然水平太差，敌军最多有300000颗导弹，导弹只能按顺序打，因为外挂有BUG,而且是超音速导弹，只有一秒导弹就到了，只能编程解决；但易琢然上课不认真，平时帮他的sxy又不在，所以他只能求助于你
-
有n颗导弹(n<=300000),求易琢然开一个外挂最多能拦截多少导弹，开几个外挂才能打掉所有导弹？
输入
- 一行，依次为n颗导弹的高度(0<高度<2147483647) 输出
- 第一行，一个外挂最多能拦截多少导弹；第二行，开几个外挂才能打掉所有导弹 样例输入
-
389 207 155 300 299 170 158 65
样例输出
-
6 2
题目思路
-
第一问：求最长不上升子序列。
第二问：求最长上升子序列。
数据大，使用O（N*N）的方法不可行，要是用O（Nlog（N））的方法
-
题目代码
#include <cstdio>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#define LL long long
using namespace std;int a[300005];
int dp[300005];bool cmp(int a, int b){return a > b;
}int main(){int n = 0;while(scanf("%d",&a[n++]) != EOF); n--;int len = 1; dp[1] = a[0];for(int i = 1; i < n; i++){if(a[i] <= dp[len])dp[++len] = a[i];else{int pos = upper_bound(dp+1,dp+len,a[i],cmp) - dp;dp[pos] = a[i];}}printf("%d\n",len);len = 1; dp[1] = a[0];for(int i = 1; i < n; i++){if(a[i] > dp[len])dp[++len] = a[i];else{int pos = lower_bound(dp+1,dp+len,a[i]) - dp;dp[pos] = a[i];}}printf("%d",len);return 0;
}