首先贴出题目链接：P1020 [NOIP1999 普及组] 导弹拦截
代码很简单，但其实每一行都有它的道理。别急，看完代码继续往下看?

#include<bits/stdc++.h>
using namespace std;
const int MAXN=100010;
int n=1;
int ans1=1,ans2=1;
int arr[MAXN],len[MAXN],f[MAXN];
bool cmp(int x,int y)
{
	return x>y;
}
int main()
{
	while(cin>>arr[n])
		n++;
	n--;//因为n最后多加了个1
	len[1]=f[1]=arr[1];
	for(int i=2;i<=n;i++)
	{
		if(len[ans1]>=arr[i]) len[++ans1]=arr[i];
		else len[upper_bound(len+1,len+1+ans1,arr[i],cmp)-len]=arr[i];
		if(f[ans2]<arr[i]) f[++ans2]=arr[i];
		else f[lower_bound(f+1,f+1+ans2,arr[i])-f]=arr[i];
	}
	cout<<ans1<<'\n'<<ans2;
	return 0;
}

从算法上分析

第一个数字

第一个数字要求我们表示这套系统最多能拦截多少导弹，而题目中又说拦截的导弹的高度后面的不能大于前面的，要让我们求最大值，我们将拦截的导弹的高度看成一个序列，很明显，这是在求最长不升子序列（注意没有“连续”字眼）

在求第一个数字，假设我们遍历到的导弹为i，导弹高度为len[i]，系统高度已经为l，很明显我们需要一个if来判断len[i]与l的关系，如果导弹高度小于系统高度，那就无脑强行塞进拦截序列里面，答案数++
但如果导弹高度大于系统高度，怎么办呢，那我们还是要充分榨干它的剩余价值利用这枚导弹，我们找到比这枚导弹更低且与这枚导弹高度最接近的导弹（在严格降序的序列中，就是第一个小于这枚导弹高度的导弹），然后直接把它替换成当前导弹

为什么？

• 如果被替换的导弹在拦截序列末尾，那么替换后末尾更高了，也就是说后面可以放下更多的导弹
• 如果被替换的导弹在序列中间，我们有以下证明：
  令我们找到的导弹高度为$Le{n}_i$，被替换的导弹高度为$Le{n}_j$，由于我们找的是比这枚导弹更低的导弹，有$$Le{n}_i>Le{n}_j$$而由于拦截序列是个降序序列，因此有$$Le{n}_{j-1}>Le{n}_j>Le{n}_{j+1}$$又因为$j$是第一个小于$i$的，换句话说，$j$之前的都大于$i$，因此有$$Le{n}_{j-1}>Le{n}_i$$
  因此我们推出$$Le{n}_{j-1}>Le{n}_i>Le{n}_j>Le{n}_{j+1}$$满足了降序

第二个数字

第二个数字要表示如果要拦截所有导弹，最少要配备多少套这种导弹拦截系统，那么你这些导弹高度降低是可以的，我们就不用另开一套拦截系统，等于也是没问题的，但是不能大于，一旦大于就要再来一套系统。而且我们要注意两点关键信息：

• 一是导弹序列是有序的，你不能先把导弹排一遍序，然后从高到低打
• 二是要拦截所有导弹，因此你要囊括整个序列，不能因为某个导弹太高就放弃它
  综合以上两点，我们需要一个不漏按顺序把所有导弹遍历完，顺序固定，这反而降低了题目难度

接下来就是玄学时间：
有一种东西，叫Dilworth定理，它的意思是“将一个序列剖成若干个单调不升子序列的最小个数等于该序列最长上升子序列的个数”
也就是说，所有拦截系统的数量为导弹序列的最长上升子序列的元素个数。

怎么样？是不是很懵，我们还可以换一种理解方式

我们已经打到第i个导弹时，有j个系统，我们需要把前j个系统都遍历一遍，找到系统当前高度≥导弹i高度并使两者高度差最小的系统，然后系统当前高度更新为导弹i高度。如果没找到，那么系统数 j++

其实我们把这段代码写出来后，会发现这与求最长上升子序列的代码惊人地相似

其实你按照题意来理解或是按照某某子序列的方式来理解都可以，只是你要知道接下来写的代码不只适用于这道题，还是求最长不升子序列和最长上升子序列的二分板子

从实现方式来分析

在上文中，我们已经确定了目标，那么接下来我们说一下代码的实现
有趣的是，这道题可以用STL中的upper_bound()和lower_bound()来做

第一个数字

经过分析，我们的目标为：

如果当前导弹高度≤系统高度，无脑放入
如果当前导弹高度>系统高度，就找到第一个小于这枚导弹高度的导弹替换

“找到第一个小于……”这句话很熟悉，对了，它是upper_bound()，它可以用在有序序列中，而此时的len序列正是不升序列。但是它不是用来求“找到第一个大于”的吗，错了，upper_bound()还有它的第二形态

template<class ForwardIt, class T, class Compare>
ForwardIt lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    ForwardIt it;
    typename std::iterator_traits<ForwardIt>::difference_type count, step;
    count = std::distance(first, last);
 
    while (count > 0) {
        it = first;
        step = count / 2;
        std::advance(it, step);
        if (comp(*it, value)) {//comp此处是一个函数参数
            first = ++it;
            count -= step + 1;
        }
        else
            count = step;
    }
    return first;
}

看到了这个大大的comp了吗？没错，就像sort一样，upper_bound()可以自定义搜索规则
所以我们只需要编写一个cmp()函数

bool cmp(int x,int y)
{
	return x>y;//降序
}

就可以在降序序列当中找“第一个小于”啦
当然如果你还想偷懒……
你可以用这个greater<int>()，它与上面的cmp是等价的
以下两种写法均可

upper_bound(len+1,len+1+ans1,arr[i],cmp)
upper_bound(len+1,len+1+ans1,arr[i],greater<int>())

而upper_bound返回的是一个指针，我们需要用它的返回值减去数组头指针来得到这是第几个数
第一个数字完整代码如下

if(len[ans1]>=arr[i]) len[++ans1]=arr[i];
else len[upper_bound(len+1,len+1+ans1,arr[i],cmp)-len]=arr[i];

第二个数字

第二个数字，我们的目标为

我们已经打到第i个导弹时，有j个系统，我们需要把前j个系统都遍历一遍，找到系统当前高度≥导弹i高度并使两者高度差最小的系统，然后系统当前高度更新为导弹i高度。如果没找到，那么系统数 j++

“找到系统当前高度≥导弹i高度并使两者高度差最小的系统”也就是说在升序序列中找到第一个大于等于导弹i的，很明显，lower_bound()

思路很明晰，直接上代码

if(f[ans2]<arr[i]) f[++ans2]=arr[i];
		else f[lower_bound(f+1,f+1+ans2,arr[i])-f]=arr[i];

最终，这道题就毫 不 费 力做出来了！

FAQ

upper_bound()和lower_bound()有什么区别
upper_bound()是在升序队列里找第一个大于指定数的数
lower_bound()是在升序队列里找第一个大于等于指定数的数
这两个玩意就只差一个“等于”
千万不要把lower_bound()记成“小于等于”了！