傳送門(mén)
先介紹一下lower_bound和upper_bound嚼鹉；
lower_bound
??lower_bound可以二分找到數(shù)據(jù)序列中第一個(gè)大于等于x的數(shù)
??lower_bound默認(rèn)隊(duì)列中的數(shù)據(jù)是從小到大進(jìn)行排序的星虹，使用方法是lower_bound( begin, end, num)。假定對(duì)于a數(shù)組泰演，例如從[1呻拌，len）區(qū)間里查找第一個(gè)大于等于x的數(shù)lower_bound(a+1, a+1+len, x)葱轩。從[0睦焕，len）區(qū)間里查找第一個(gè)大于等于x的數(shù)lower_bound(a, a+len, x)。假如查到該數(shù)靴拱，就返回這個(gè)數(shù)的地址垃喊，如果查不到，則返回隊(duì)列的末尾end袜炕。那么我們?nèi)绾未_定他的下標(biāo)呢本谜，很簡(jiǎn)單，只需要減去數(shù)組的起始地址就能得到偏移量也就是他的下標(biāo)了偎窘。比如:
int k = lower_bound(a, a+len, x) - a;//k就是在數(shù)組a中第一個(gè)大于等于x的元素的下標(biāo)
... = a[k];
??這里多插一句隊(duì)列的末尾在哪乌助，end在隊(duì)列中最后一個(gè)元素的后邊，如下表所示陌知，8個(gè)元素的隊(duì)列他托，end在第8個(gè)元素的后面：
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | end |
|---|
對(duì)于下列這個(gè)具體的數(shù)據(jù)序列,長(zhǎng)度len = 8，找第一個(gè)大于等于3的元素仆葡。
| A序列的序號(hào) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 值 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 5 |
k = lower_bound(A,A+len,3) - A赏参； 此時(shí)k = 1，也就是該元素在序列中的位置沿盅。
??這是對(duì)于非下降序列來(lái)說(shuō)的把篓，可以找到第一個(gè)大于等于x的數(shù)，那么對(duì)于非上升序列呢腰涧，我們?nèi)フ乙粋€(gè)小于等于x的數(shù)韧掩，這樣寫(xiě)就不對(duì)了，就需要更改lower_bound的默認(rèn)比較器窖铡，從其默認(rèn)的“”改成“
”疗锐，這就需要我們手寫(xiě)一個(gè)比較器。
bool cmp(const int& a, const int& b){return a > b;}
int k = lower_bound(a, a + n, x, cmp) - a;
或者我們可以使用STL自帶的比較器万伤，greater<int>()提供了一個(gè)大于函數(shù)窒悔。
int k = lower_bound(a + 1, a + 1 + n, x, greater<int>() ) - a;
upper_bound
upper_bound與lower_bound最大的不同，upper_bound找到的是第一個(gè)x的數(shù)敌买。再拿上邊的數(shù)組為例简珠，長(zhǎng)度len = 8，找第一個(gè)大于3的元素。
| A序列的序號(hào) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 值 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 5 |
k =upper_bound(A,A+len,3) - A聋庵； 此時(shí)k = 5膘融。
從另一種方面來(lái)解釋
??對(duì)于lower_bound(array, array+len, x)，相當(dāng)于找到的是在保持序列仍有序時(shí)祭玉，x所能插入到原序列的最前的位置氧映。而對(duì)于upper_bound(array, array+len, x)是保持原序列有序時(shí)，所能插入到原序列的最后的位置脱货。
以3為例,可插入到元素之前的位置
| A序列的序號(hào) | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 值 | 2 | 3 | 3 | 3 | 3 | 4 | 4 | 5 |
| 可插入位置 | ||||||||
| lower | upper |
插入到上面帶箭頭的位置的元素之前岛都，都可以保證插入后的元素有序。
最長(zhǎng)上升子序列（LIS）
最長(zhǎng)下降子序列（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;
}
非常簡(jiǎn)單的測(cè)試用代碼
#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;
}
