（神里……）

先来复习一下C++STL库函数的二分查找lower_bound和upper_bound。
lower_bound求的是序列中第一个大等于目标元素，返回其位置，upper_bound求的是序列中第一个大于目标元素的位置。
序列{\(a _ n\)}下标从1开始，二者的形式：

int k = lower_bound(a + 1，a + n + 1, x) - a。
int k = upper_bound(a + 1, a + n + 1, x) - a。

使用二者时要保证序列时升序的，当然，其他情况也可以使用，需要添加自定义比较。

 bool cmp(const int& a,const int& b){
     return a>b;
 }
 lower_bound(a,a+n,val,cmp);
 upper_bound(a,a+n,val,cmp); 

还有其他写法：

lower_bound(a,a+n,val,greater<int>());
upper_bound(a,a+n,val,greater<int>());

再介绍一个前置知识Dilworth定理。
内容是：对偏序集<A，≤>，设A中最长链的长度是n，则将A中元素分成不相交的反链，反链个数至少是n。
（这个定理对解决下面的这道题目很有帮助）

P1020

[NOIP1999 普及组] 导弹拦截

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

一行，若干个整数，中间由空格隔开。

输出格式

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

样例 #1

样例输入 #1

389 207 155 300 299 170 158 65

样例输出 #1

6
2

提示

对于前 \(50\%\) 数据（NOIP 原题数据），满足导弹的个数不超过 \(2000\) 个。该部分数据总分共 \(100\) 分。可使用\(\mathcal O(n^2)\) 做法通过。
对于后 \(50\%\) 的数据，满足导弹的个数不超过 \(10^5\) 个。该部分数据总分也为 \(100\) 分。请使用 \(\mathcal O(n\log n)\) 做法通过。

对于全部数据，满足导弹的高度为正整数，且不超过 \(5\times 10^4\)。

此外本题开启 spj，每点两问，按问给分。

\(\text{upd 2022.8.24}\)：新增加一组 Hack 数据。

解析

题目相当于有两个问。
第一个问是求序列中的最长不上升子序列，需要用\(O(nlogn)\)的方法，类比求最长上升子序列，使用二分就能解决。
对于第二问，通过Dilworth定理，我们可以推出最少的不上升子序列的个数就是最长上升子序列的长度。 直接运用该结论即可，求序列的最长上升子序列，还是用二分的方式。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n, a[N], dp1[N], dp2[N], len1, len2;
signed main() {
	while (~scanf("%d", &a[++ n]));
	n --, len1 = len2 = 1;
	dp1[1] = a[1], dp2[1] = a[1];
	for (int i = 2; i <= n; i ++) {
		if (a[i] <= dp1[len1]) dp1[++ len1] = a[i];
		else{
			int k = upper_bound(dp1 + 1, dp1 + len1 + 1, a[i], greater<int>()) - dp1;
			dp1[k] = a[i];
		}
		if (a[i] > dp2[len2]) dp2[++ len2] = a[i];
		else {
			int k = lower_bound(dp2 + 1, dp2 + len2 + 1, a[i]) - dp2;
			dp2[k] = a[i];
		}
	}
	cout << len1 << '\n';
	puts("");
	cout << len2 << '\n';
	return 0;
}

花这么长时间只搞了一道普及难度的题…(恐怖如斯…qwq)

原文地址：https://www.cnblogs.com/YHxo/p/16786993.html