题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

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

输入格式

共一行，输入导弹依次飞来的高度。

输出格式

第一行包含一个整数，表示最多能拦截的导弹数。

第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围

雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。

算法1

(贪心 与 二分) $O(nlogn)$

时间复杂度

参考文献

C++ 代码

#include <bits/stdc++.h>

using namespace std ;

const int N = 100001 ;

int n ;
int len = 1 ;
int f[N] ;
int p[N] ;
int a[N] ;

void second ( ) {

    len = 1 ;
    p[1] = a[1] ;

    for ( int i = 2 ; i <= n ; i ++ ) {

        if ( a[i] > p[len] ) p[++ len] = a[i] ;

        else  p[lower_bound ( p + 1 , p + 1 + len , a[i] ) - p] = a[i] ;

    }

    cout << len ;

}

int main ( ) {

    int k = 1 ;

    while ( cin >> a[k] ) {

        k ++ ;
        n ++ ;

    } 

    f[1] = a[1] ;

    for ( int i = 2 ; i <= n ; i ++ ) {

        if ( a[i] <= f[len] ) f[++ len] = a[i] ;

        else  f[upper_bound ( f + 1 , f + 1 + len , a[i] , greater < int > ( ) ) - f] = a[i] ;

    }

    cout << len << endl ;

    second ( ) ;

    return 0 ;

}