大理石在哪儿 Where is the Marble? UVa 10474
2018-06-17 21:56:22来源：未知 阅读 ()
描述
现有N个大理石，每个大理石上写了一个非负整数、首先把各数从小到大排序
然后回答Q个问题。每个问题问是否有一个大理石写着某个整数x，如果是，还要
回答哪个大理石上写着x。排序后的大理石从左到右编号为1~N。(在样例中，为了
节约篇幅，所有大理石的数合并到一行，所有问题也合并到一行。)
样例输入：
4 1
2 3 5 1
5
5 2
1 3 3 3 1
2 3
样例输出：
CASE# 1：
5 found at 4
CASE# 2：
2 not found
found at 3
1 #include <iostream> 2 #include <algorithm> 3 4 using namespace std; 5 6 main() 7 { 8 int n, q, x, a[10000], k = 0; 9 while(cin >> n >> q) 10 { 11 cout << "CASE#" << k << ":" << endl; 12 k++; 13 for(int i = 0; i < n; i++) 14 { 15 cin >> a[i]; 16 } 17 sort(a, a+n); 18 while(q--) 19 { 20 cin >> x; 21 int p = lower_bound(a, a+n, x) - a; //在已知数组a中寻找x 22 if(a[p] == x) 23 cout << x << " found at " << p << endl; 24 else 25 cout << x << " not found" << endl; 26 } 27 } 28 }
STL中关于二分查找的函数有三个lower_bound 、upper_bound 、binary_search 。这三个函数都运用于有序区间（当然这也是运用二分查找的前提），下面记录一下这两个函数。
ForwardIter lower_bound(ForwardIter first, ForwardIter last,const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于等于值val的位置。
ForwardIter upper_bound(ForwardIter first, ForwardIter last, const _Tp& val)算法返回一个非递减序列[first, last)中的第一个大于值val的位置。
以上函数和二分查找可参考：
http://www.cnblogs.com/cobbliu/archive/2012/05/21/2512249.html
http://blog.csdn.net/EbowTang/article/details/50770315
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
上一篇：vmmap实现
下一篇：Qt--自定义Model
- sql 删除多项 2018-06-18
- 类型参数约束 : Controller where T : class,new() 2018-06-18
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
