一坏快、lower_bound與upper_bound
1.作用
假設(shè)我們查找x，那么：
lower_bound在一個(gè)遞增序列中找出第一個(gè)大于等于x的數(shù)
upper_bound在一個(gè)遞增序列中找出序列中第一個(gè)大于x的數(shù)
2守呜、用法
對(duì)于一個(gè)數(shù)組a，在[1,n]的區(qū)間內(nèi)查找大于等于x的數(shù)，函數(shù)就寫成：
lower_bound(a + 1, a + 1 + n, x);
函數(shù)返回一個(gè)指向y的指針
//對(duì)比sort函數(shù)
sort(a, a + 1 + n, cmp);
3查乒、注意事項(xiàng)
STL的順序都是默認(rèn)升序的
若是
lower_bound(a + 1, a + 1 + n, x, greater <int> () );//greater代表從大到小
不上升序列長(zhǎng)度
O(nlogn)求出最長(zhǎng)不上升子序列的長(zhǎng)度
用b數(shù)組表示最終的不上升序列弥喉，
for(int i=2;i<=len;i++){
if(a[i]<=b[ls]){//如果小于等于，就放入
b[++ls]=a[i];
}else{//找出第一個(gè)比這個(gè)數(shù)小的數(shù)
*upper_bound(b+1,b+1+ls,a[i],greater<int>())=a[i];
}
}
上升序列長(zhǎng)度
int solve2(){
int ans, f[100010];
f[0] = 0;
ans = 0;
for (int i = 1; i <= n; i++){
if (a[i] > f[ans])
f[++ans] = a[i];
else{
int k = lower_bound(f, f + ans + 1, a[i]) - f;
f[k] = a[i];
}
}
return ans;
}
