现在的位置: 首页 > 综合 > 正文

UVa10474 Where is the Marble ? 有序数组二分找值,lower_bound / upper_bound

2018年12月19日 ⁄ 综合 ⁄ 共 605字 ⁄ 字号 评论关闭

题意:

给出n个数,先把各数从小到大排序,然后q次询问xi在数组中的位置,不存在则输出相应信息。


输入样例:

4 1
2
3
5
1
5
5 2
1
3
3
3
1
2
3
0 0


输出样例:

CASE# 1:
5 found at 4
CASE# 2:
2 not found
3 found at 3


//=======================================

数组从小到大有序。

lower_bound :查找“大于或者等于x”的第一个位置。

upper_bound:查找“大于x”的第一个位置。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 5;
int a[maxn];

int main()
{
    int cas = 1, x;
    int n, q;
    while(~scanf("%d%d", &n, &q)) {
        if(n==0&&q==0) break;
        for(int i=1; i<=n; ++i) {
            scanf("%d", &a[i]);
        }
        sort(a+1, a+n+1);
        printf("CASE# %d:\n", cas++);
        while(q--){
            scanf("%d",&x);
            int p = lower_bound(a+1, a+n+1, x) - a;
            if(a[p]==x){ printf("%d found at %d\n", x, p);}
            else printf("%d not found\n", x);
        }
    }
    return 0;
}

抱歉!评论已关闭.