题目

本博客给出本题截图：

首先需要 说明：这个题目在 AcWing 中也有一模一样的题目，但是两个题目的数据范围不同：

AcWing：AcWing 1010. 拦截导弹

洛谷：P1020 [NOIP1999 普及组] 导弹拦截

洛谷 中的数据范围更大，本题提供两个代码，第一个代码在 AcWing 中可以 AC，但是在洛谷中有一半的数据会 TLE，第二个代码则在洛谷中也可以过掉

AC代码1

代码解释：

f数组表示的是在前 i 个导弹中的最长不上升子序列的长度，最后对所有的 f[i] 取一个最大值即可

g数组存储的是每一个防伪系统中的结尾导弹高度，对于每一个 h 数组中的元素，我们都会有两种选择，开一个新的防卫系统，或者是接到某一个系统的结尾

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int f[N];
int g[N];
int h[N];
int n;
int main()
{
  while (scanf("%d", &h[n]) != EOF) n ++;
  int res = 0;
  for (int i = 0; i < n; i ++ ) 
  {
    f[i] = 1;
    for (int j = 0; j < i; j ++ ) 
      if (h[j] >= h[i]) 
        f[i] = max(f[i], f[j] + 1);
    res = max(res, f[i]);
  }
  printf("%d\n", res);
  int cnt = 0;
  for (int i = 0; i < n; i ++ )
  {
    int k = 0;
    while (k < cnt && g[k] < h[i]) k ++;
    g[k] = h[i];
    if (k >= cnt) cnt ++;
  }
  printf("%d\n", cnt);
  return 0;
}

upper_bound 和 lower_bound

介绍第二个代码之前先来介绍一下lower_bound 和 upper_bound，使用案例见博客：STL—algorithm（2）

若数组升序排列：

lower_bound(begin, end, a) 返回数组[begin, end)之间第一个大于或等于a的地址，找不到返回end

upper_bound(begin, end, a) 返回数组[begin, end)之间第一个大于a的地址，找不到返回end

若数组降序排列：

lower_bound(begin, end, a, greater<int>()) 返回数组[begin, end)之间第一个小于或等于a的地址，找不到返回end

upper_bound(begin, end, a, greater<int>()) 返回数组[begin, end)之间第一个小于a的地址，找不到返回end

注意：在使用这两个函数之前一定需要保证数组是有序的

AC代码2

代码解释：

本题中数组的作用在代码部分已经进行了标注，注意根据对于数组的定义，两个数组肯定是有序的

这个题说白了就是求一个最长不上升序列的长度 （不是子序列） 和一个最长上升序列的长度 （不是子序列）

求最长上升序列的长度：

求这个序列的长度实际上就是在求这套系统最多能拦截多少导弹：从前往后依次去看导弹的高度，只会有两种情况：

1.这个导弹的高度要小于等于f数组末尾的高度，那么我们就把这个导弹高度插入到我们的f数组的末尾

2.这个导弹的高度要大于f数组末尾的高度，那么我们就在f数组中找到第一个小于它的数，这里就需要用到upper_bound，然后用这个导弹的高度，去替换掉我们找到的这个数

为什么要替换掉呢？我们把上述中的导弹高度称为a，要被替换掉的导弹的高度称为b，那么如果b在末尾，那么由于b < a，所以b后面能接的导弹数不如a的多，如果b在内部，那么b在有生之年内绝对不会再被用到了，所以把他替换掉也是无所谓的事情，注意在进行上述的一切操作中，我们的f数组内部都是有序的，读者可以想一下是为什么.

再次强调：我们求的是最长上升序列的长度，不是子序列！！！

最长上升序列的长度：求法和思路同上述，这里就不再进行过多的赘述

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int f[N];  //f数组存储的是最长不上升序列（注意不是子序列） 
int g[N];  //g数组存储的是最长上升序列（注意不是子序列）
int h[N];
int n;
int main() 
{
  while (cin >> h[++ n]);
  n --;
  int res = 1, cnt = 1;
  f[1] = g[1] = h[1];
  for (int i = 2; i <= n; i ++ ) 
  {
    if (h[i] <= f[res]) f[++ res] = h[i];
    else
    {
      int k = upper_bound(f + 1, f + res + 1, h[i], greater<int>()) - f;
      f[k] = h[i];
    }
    if (h[i] > g[cnt]) g[++ cnt] = h[i];
    else
    {
      int k = lower_bound(g + 1, g + cnt + 1, h[i]) - g;
      g[k] = h[i];
    }
  }
  printf("%d\n%d\n", res, cnt);
  return 0;
}

总结

才疏学浅，第一次真正运用到 lower_bound 和 upper_bound，真香.