传送门
先介绍一下lower_bound和upper_bound；
lower_bound
lower_bound可以二分找到数据序列中第一个大于等于x的数
lower_bound默认队列中的数据是从小到大进行排序的，使用方法是lower_bound( begin, end, num)。假定对于a数组，例如从[1，len）区间里查找第一个大于等于x的数lower_bound(a+1, a+1+len, x)。从[0，len）区间里查找第一个大于等于x的数lower_bound(a, a+len, x)。假如查到该数，就返回这个数的地址，如果查不到，则返回队列的末尾end。那么我们如何确定他的下标呢，很简单，只需要减去数组的起始地址就能得到偏移量也就是他的下标了。比如:
int k = lower_bound(a, a+len, x) - a;//k就是在数组a中第一个大于等于x的元素的下标
... = a[k];
这里多插一句队列的末尾在哪，end在队列中最后一个元素的后边，如下表所示，8个元素的队列，end在第8个元素的后面：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | end |
|---|
对于下列这个具体的数据序列,长度len = 8，找第一个大于等于3的元素。
| A序列的序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 值 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 5 |
k = lower_bound(A,A+len,3) - A； 此时k = 1，也就是该元素在序列中的位置。
这是对于非下降序列来说的，可以找到第一个大于等于x的数，那么对于非上升序列呢，我们去找一个小于等于x的数，这样写就不对了，就需要更改lower_bound的默认比较器，从其默认的“”改成“
”，这就需要我们手写一个比较器。
bool cmp(const int& a, const int& b){return a > b;}
int k = lower_bound(a, a + n, x, cmp) - a;
或者我们可以使用STL自带的比较器，greater<int>()提供了一个大于函数。
int k = lower_bound(a + 1, a + 1 + n, x, greater<int>() ) - a;
upper_bound
upper_bound与lower_bound最大的不同，upper_bound找到的是第一个x的数。再拿上边的数组为例，长度len = 8，找第一个大于3的元素。
| A序列的序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 值 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 5 |
k =upper_bound(A,A+len,3) - A； 此时k = 5。
从另一种方面来解释
对于lower_bound(array, array+len, x)，相当于找到的是在保持序列仍有序时，x所能插入到原序列的最前的位置。而对于upper_bound(array, array+len, x)是保持原序列有序时，所能插入到原序列的最后的位置。
以3为例,可插入到元素之前的位置
| A序列的序号 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 值 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 5 |
| 可插入位置 | ||||||||
| lower | upper |
插入到上面带箭头的位置的元素之前，都可以保证插入后的元素有序。
最长上升子序列（LIS）
最长下降子序列（LDS）
思路
AC代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define maxn 1000100
int d[maxn], f[maxn], t[maxn];
int main(){
int k = 0;
while(scanf("%d", &d[k]) != EOF){
k++;
}
int len = 1;
f[len] = d[0];
int len1 = 1;
t[len1] = d[0];
for(int i = 1; i < k; i++){
if(d[i] <= f[len]){
len++;
f[len] = d[i];
}else{
int b = upper_bound(f+1, f+len+1, d[i], greater<int>()) - f;
f[b] = d[i];
}
if(d[i] > t[len1]){
len1++;
t[len1] = d[i];
}else{
int b = lower_bound(t+1,t+len1+1,d[i])-t;
t[b] = d[i];
}
}
cout << len << endl;
cout << len1 << endl;
return 0;
}
非常简单的测试用代码
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[] = {2, 3, 3, 3, 3, 4, 5, 6};
int k1 = lower_bound(a, a+8, 3) - a;
int k2 = upper_bound(a, a+8, 3) - a;
cout << "lower_bound: " << k1 << endl;
cout << "upper_bound: " << k2 << endl;
}
网友评论