lower_bound与upper_bound还有fill的使用

本文主要是介绍lower_bound与upper_bound还有fill的使用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

STL一直很好用，今天使用了一下lower_bound和upper_bound函数，熟练使用可以减少写二分的时间。

lower_bound是二分查找出大于等于给出的数的第一个值。upper_bound是二分查找出大于给出的数的第一个值。

这两个函数都是返回的地址，所以使用还要减去首地址（如果数组里面保存的是int）

下面是使用lower_bound优化最长上升子序列。由于长度相同的上升子序列只需要保存结尾最小的那个，而长度递增时，结尾数字的大小也是递增的。最长上升子序列就是找出比他大的第一个数。前面的数都比他小，所以他和这个数的长度相同。然后由于他比较然后小，更新找到的那个值。

#include<stdio.h>
#include<string.h>
#include<algorithm>using namespace std;int num[10]={3,6,3,2,4,6,7,5,4,3};const int INF=0x3f3f3f3f;
int l=10;
int g[100];
int d[100];
int main()
{fill(g,g+l,INF);int max_=-1;for(int i=0;i<l;i++){int j=lower_bound(g,g+l,num[i])-g;d[i]=j+1;if(max_<d[i])max_=d[i];g[j]=num[i];}printf("%d\n",max_);return 0;
}

这篇关于lower_bound与upper_bound还有fill的使用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---