關于lower_bound和upper_bound

不說廢話，直接上G++原始碼

#include

upper_bound

template <class ForwardIterator, class T>
  ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = std::distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; std::advance (it,step);
    if (!(val<*it))                 // or: if (!comp(val,*it)), for version (2)
      { first=++it; count-=step+1;  }
    else count=step;
  }
  return first;
}

lower_bound

template <class ForwardIterator, class T>
  ForwardIterator lower_bound (ForwardIterator first, ForwardIterator last, const T& val)
{
  ForwardIterator it;
  iterator_traits<ForwardIterator>::difference_type count, step;
  count = distance(first,last);
  while (count>0)
  {
    it = first; step=count/2; advance (it,step);
    if (*it<val) {                 // or: if (comp(*it,val)), for version (2)
      first=++it;
      count-=step+1;
    }
    else count=step;
  }
  return first;
}

演算法：

可以看到：演算法基于二分思想，用了 的distance( *start_iterator , *end_iterator)計算迭代器距離

限制：

無論是使用upper_bound還是lower_bound 都要是一個絕對升序容器的迭代器結點，無序的演算法失效，因為二分基于有序，至于降序為什么不行你得問問寫STL的前輩大佬們，，，不過這個函式可以加一個引數來改變他的做法，文章后面（擴展）中有詳細講解

作用：

upper_bound( *start, *end , &val )用來找到一個有序容器中第一個比val大的迭代器， 只能嚴格的大于，不能等于.

lower_bound( *start , *end , &val )用來找到一個有序容器中最后一個不大于val的迭代器，可以小于并且等于，但是是最后一個，也就是第一個大于等于他的數

從演算法可以看出：無論是upper_bound還是lower_bound 如果都大于容器中全部元素，那么回傳結果只能是容器一個迭代器

@Tip

在線除錯C/C++代碼，這個網站真的NB http://cpp.sh 可惜沒有高亮，沒有語意提示，沒有自動補全，

實體：

vector v; {10 10 20 20 30 30 40 50 60 100}

我們規定 ans代表函式回傳的迭代器，*ans為解參考

讀者可以自己試一下，他們兩個只是差了一個等于號

注意：

容器一定要是順序序列，不然會出現相當詭異的結果

擴展：upper_bound/lower_bound傳第四個引數

上原始碼

default (1)	
template <class ForwardIterator, class T>

ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,

const T& val);
custom (2)
template <class ForwardIterator, class T, class Compare>

ForwardIterator upper_bound (ForwardIterator first, ForwardIterator last,

const T& val, Compare comp);

模板類有兩個默認方法，其中第二個可以傳遞比較器函式指標

一般為了炫技，這個函式不會自己寫，用greater() 來代替

這個比較器指標是為了把lower_bound或者upper_bound變成一個有等于號的降序查找函式

就是說原來的陣列順序是：

10 10 20 20 30 30 40 50 60 100

現在是：

100 60 50 40 30 30 20 20 10 10

也就是找到第一個大于或者最后一個等于他的元素

Application

洛谷P1020導彈攔截:https://www.luogu.com.cn/problem/P1020，也是dp演算法的經典題目

這個題就是用O（n*logn）方法同時分別找到一個最長不上升子序列和一個最長上升子序列的長度即可

回顧一下LIS（Longest Icrement Sequence）的O（n*logn）演算法

我們用陣列來表示堆疊

找到最長不上升子序列

if(要填進去這個數字小于等于堆疊頂元素) 直接push
else 用*upper_bound( * start , *end , &val ，greater<int>())=val

找到最長上升子序列

if(要填進去這個數字大于堆疊頂元素) 直接push
else 用*lower_bound( *start  ,*end  ,&val)=val

結語：

動態規劃這個演算法很好的整合了這個演算法，和二分一起雄霸天下了！！！時間復雜的是非常優秀的，我的代碼當中加入了O8快讀read()，請別問我為什么這么寫，

最后給一下AC代碼

#include<iostream>
#include<cstdio>
#include<algorithm>
#define R register
using namespace std;
const int N=100010;
int a[N],d1[N],d2[N],n;
inline bool read(int &x) {
    char c=getchar();
    if(c==EOF)return false;
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9') {
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return true;
}
int main() {
    while(read(a[++n]));n--;
    R int len1=1,len2=1;
    d1[1]=d2[1]=a[1];
    for(R int i=2; i<=n; i++) {
        if(d1[len1]>=a[i])d1[++len1]=a[i];
        else *upper_bound(d1+1,d1+1+len1,a[i],greater<int>())=a[i];
        if(d2[len2]<a[i])d2[++len2]=a[i];
        else *lower_bound(d2+1,d2+1+len2,a[i])=a[i];
    }
    printf("%d\n%d",len1,len2);
    return 0;
}

標籤：C++

上一篇：制作游戲時，如何管理游戲資源? 逐行注釋！

下一篇：好用的C語言編程軟體！工具都沒有，怎么用技術改變世界呢！