首页 > 代码库 > 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)