首页 > 代码库 > UVa Where is the Marble? (STL)
UVa Where is the Marble? (STL)
链接:http://acm.hust.edu.cn/vjudge/problem/19833
分析:sort和lower_bound函数的应用。sort可以对任意对象排序,但需要定义“小于”运算符,或在排序时传入一个“小于”函数。普通数组用sort(a, a + n)的方式调用,vector用sort(v.begin(), v.end())的方式调用。排序后可以用lower_bound查找“大于或等于x的第一个位置”。本题将所有大理石按升序排好后,用lower_bound查找大于或等于询问整数在数组中的第一个位置,然后判断x是否存在,存在则输出位置p+1。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int maxn = 10000; 6 int a[maxn]; 7 8 int main() { 9 int n, q, kase = 0;10 while (scanf("%d%d", &n, &q) == 2 && n) {11 printf("CASE# %d:\n", ++kase);12 for (int i = 0; i < n; i++) scanf("%d", &a[i]);13 sort(a, a + n);14 while (q--) {15 int x; scanf("%d", &x);16 int p = lower_bound(a, a + n, x) - a;17 if (a[p] == x) printf("%d found at %d\n", x, p + 1);18 else printf("%d not found\n", x);19 }20 }21 return 0;22 }
UVa Where is the Marble? (STL)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。