STL函数 lower_bound 和 upper_bound 在算法竞赛中的用法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了STL函数 lower_bound 和 upper_bound 在算法竞赛中的用法,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1060字,纯文字阅读大概需要2分钟。
内容图文
![STL函数 lower_bound 和 upper_bound 在算法竞赛中的用法](/upload/InfoBanner/zyjiaocheng/645/48604876b1fe427c927f2fdd37e3d24f.jpg)
以前比较排斥这两个函数,遇到二分都是手写 \(while(left<=right)\)。
这次决定洗心革面记录一下这两个函数的在算法竞赛中的用法,毕竟一般不会导致TLE。
其实百度百科已经概述得比较清楚了,
我们假设 \(value\) 为一个给定的数值,
\(lower\_bound\) 是在一个升序序列中从前后后找第一个大于等于 \(value\) 的值,
\(upper\_bound\) 是在一个升序序列中从前后后找第一个大于 \(value\) 的值。
比如:\(lower\_bound(a+1,a+n+1,k)\) 就是在\(a\)数组的\([1,n]\)范围(必须升序)里从前到后找第一个大于等于\(k\)的值,并以指针的形式返回。
注意,这两个函数的返回值都是一个指针,指向原序列中可以插入value,而不会破坏容器顺序的第一个位置。
我们可以在指针函数前面加个取值符 * ,来获得想得到的值。
看到这里,你应该知道lower和upper这两个单词的含义的吧,即将value插入某位置后该序列仍然分别是单调不严格递增和单调严格递增的。
举个栗子:
int *p1,*p2;
int a[6]={3,5,6,6,7,9};
p1=lower_bound(a,a+6,6);
p2=upper_bound(a,a+6,6);
printf("内存地址: p1 -> %d p2 -> %d\n",p1,p2);
printf("在原序列中找到的值: p1 = %d p2 = %d\n",*p1,*p2);
运行结果为:
内存地址: p1 -> 7339512 p2 -> 7339520
在原序列中找到的值: p1 = 6 p2 = 7
内容总结
以上是互联网集市为您收集整理的STL函数 lower_bound 和 upper_bound 在算法竞赛中的用法全部内容,希望文章能够帮你解决STL函数 lower_bound 和 upper_bound 在算法竞赛中的用法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。