最长不上升子序列

题目描述：
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷:
虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一套系统,因此有可能不能拦截所有的导弹。
输入数据:
第一行为一个整数 N,表示飞来的导弹个数,N<=100000
第二行为 N 个整数,依次表示导弹飞来的高度,高度数据为不大于 3000000 的正整数。
输出数据:
第一行,输出计算一套系统最多能拦截多少导弹
第二行,输出要拦截所有导弹最少要配备多少套这种导弹拦截系统。

容易看出，第一问求的是这个序列的最长不上升子序列的长度。这个问题有一个N^2时间规模的DP算法，用于10^5的数据是显然超时的。本人就不讲解这个算法了，不了解的读者可以自行搜索。

=================================================================

下面介绍一个时间复杂度为NlogN的，基于贪心和二分查找的算法。（h表示飞来导弹的高度）
引入一个数组S[MAXN],它的长度记作top。S[i]表示长度为i的最长不上升序列的末尾的元素的最大值。容易知道，S是不递增的。
初始化S[1] = h[0]，top = 1
从h[1]开始，依次处理每个导弹h[i]。如果h[i] < S[top],那么S[++top] = h[i]。否则用二分查找在S[1]~S[top]中寻找恰好小于h[i]的元素，并把它替换成h[i].
处理完所有h后，top的值即为最长不上升子序列的长度。

为什么可以这么做呢？本人认为有以下几个原因：
任何时刻均有i>=top;
对于一组数据，要获得较长的不上升子序列，则序列末尾的元素要尽量大。
把S中恰好大于h[i]的元素替换后，会给替换位置后的元素更大的上升空间，可能创造更长的序列。

一个问题：能否通过S和h两个数组，重构最长不上升序列呢？请读者思考。

=================================================================

题目的第二个问题是需要几套系统可以拦截所有导弹。对于这个问题，有一个贪心的解法。
用S[i]表示第i个系统目前的高度，初始化所有S[i]为LONG_MAX。
从h[0]~h[N-1]，对每个h[i]，都在S中找出恰好>=h[i]的S[k]，令S[k] = h[i]。
最后，统计S中小于LONG_MAX的值的个数cnt即为答案。

可以发现，对任意t，S[t]的值是只减不增的，并且S是具有单调性的，因此可以用二分优化查找。总的复杂度也是NlogN.

C语言: 高亮代码由发芽网提供

//nlogn的类LIS，贪心
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 100005

long h[MAXN];
long S[MAXN];
long N;

void init()
{
   scanf("%ld\n",&N);
   long i;
   for(i = 0;i < N;i ++)
       scanf("%ld\n",h + i);
}

void solve_1()
{
   long i,top,l,r,mid;
   S[1] = h[0];
   top = 1;
   for(i = 1;i < N;i ++)
   {
       if(h[i] <= S[top])
           S[++top] = h[i];
       else
       {
           l = 1;r = top;
           while(l < r)
           {
               mid = (l + r) / 2;
               if(S[mid] < h[i])
                   r = mid;
               else
                   l = mid + 1;
           }
           S[l] = h[i];
       }
   }
   printf("%ld\n",top);
}

long find(long *v,long l,long r,long ele)   //二分查找
{
   long mid;
   while(l < r)
   {
       mid = (l + r) / 2;
       if(v[mid] < ele)
           l = mid + 1;
       else
           r = mid;
   }
   return l;
}

void solve_2()   //贪心地安排导弹，每次都使用恰好大于h[i]的导弹
{
   long i,x;
   static long v[MAXN];
   for(i = 1;i <= N;i ++)
       v[i] = 100000000;
   for(i = 0;i < N;i ++)
   {
       x = find(v,1,N,h[i]);
       v[x] = h[i];
   }
   for(i = 1;i <= N;i ++)
       if(v[i] == 100000000)    break;
   printf("%ld\n",i - 1);
}

int main()
{
   freopen("missile.in","r",stdin);
   freopen("missile.out","w",stdout);
   init();
   solve_1();
   solve_2();
   return 0;
}