题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入描述:

1行，若干个整数（个数≤100000）

输出描述:

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

示例1

输入
389 207 155 300 299 170 158 65
输出
6
2

解答

题意就是让我们求一个最长不下降子序列和一个最长上升子序列的长度
STL还是比较方便的，大致介绍一下upper_bound和lower_bound的用法
对于lower_bound,它是返回数组中第一个大于等于x的数，并返回指针。
对于upper_bound,它是返回数组中第一个大于x的数，并返回指针。
lower_bound: 
int p=upper_bound(sta1+1,sta1+len+1,a[i],greater<int>())-sta1;
我们可以把指针转化成数组下标，减去数组指针即可。与sort用法类似，注意：
这里我们找的是小于等于x的第一个数，于是用了C++自带的大于函数（实际上是更改了原函数中的<函数），即
我们考虑如何nlogn实现。
我们可以开一个栈，来模拟装入数的过程。最长上升子序列类似，就先模拟最长不上升子序列吧：
首先，第一个数一定是要入栈的，故从第二个开始枚举。设len是栈的长度，则有：
对于当前数，如果小于等于栈首，则直接入栈即可，长度+1.
如果当前数大于栈首，则我们可以找到第一个比它小的数，然后替换它。显然，对于更新后的这个数，后面可以加的数更多，类似于贪心策略。
我们可以一遍扫过，同时处理最长不下降子序列和最长上升子序列。同时，对于最长不下降子序列，我们只要找第一个小于它的数，所以用upper_bound.

代码： 

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int sta1[110000],sta2[110000];
int a[110000],len=1,len2=1,tot;
inline bool read(int &x){
    int s=0,w=1;
    char ch=getchar();
    if(ch==EOF)return false;
    while(ch<'0'||ch>'9'){
        if(ch=='-')w=-1;
        ch=getchar();
    }while(ch>=48&&ch<='9'){
        s=(s<<1)+(s<<3)+(ch^48);
        ch=getchar();
    }x=s*w;
    return true;
}int buf[500];
inline void write(int x){
    int p=0;
    if(x==0)p++;
    else while(x){
        buf[p++]=x%10;
        x/=10;
    }for(int i=p-1;i>=0;i--)putchar('0'+buf[i]);
}
int main(){
    while(read(a[++tot]));
    tot--;
    sta1[1]=a[1];
    sta2[1]=a[1];
    for(int i=2;i<=tot;++i){
        if(sta1[len]>=a[i])sta1[++len]=a[i];
        else{
            int p=upper_bound(sta1+1,sta1+len+1,a[i],greater<int>())-sta1;
            sta1[p]=a[i];
        }
        if(sta2[len2]<a[i])sta2[++len2]=a[i];
        else{
            int p=lower_bound(sta2+1,sta2+len2+1,a[i])-sta2;
            sta2[p]=a[i];
        }
    }printf("%d\n%d",len,len2);
    return 0;
}


来源：Refined_heart