大理石在哪兒（Where is the Marble？，Uva 10474）

現有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

3 found at 3

【分析】

題目意思已經很清楚了：先排序，再查找。使用algorithm頭文件中的sort和lower_bound 很容易完成這兩項操作，代碼如下：

#include<algorithm>
using namespace std;
const int maxn = 10000;
int main() {
    int n, q, x, a[maxn], kase = 0;
    while(scanf("%d%d", &n, &q) == 2 && n) {
        printf("CASE# %d:\n", ++kase);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);
    sort(a, a+n); //排序
        while(q--) {
            scanf("%d", &x);
            int p = lower_bound(a, a+n, x) - a; //在已排序數組a中尋找x
            if(a[p] == x) printf("%d found at %d\n", x, p+1);
                else printf("%d not found\n", x);
        }
    }
    return 0;
}

lower_bound 函數：

lower_bound()返回值是一個迭代器,返回指向比key大的第一個值的位置。例如：

#include <algorithm>
#include <iostream>
using namespace std;
int main()
{
    int a[]={1,2,3,4,5,7,8,9};
    printf("%d",lower_bound(a,a+8,6)-a); 
 return 0;    
}

lower_bound函數返回的是一個地址，-a之后變成下標。

不用lower_bound函數：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

int main() {
    int n,m,count=0;
    while(1){
    
    cin>>n>>m;
    if(n==0) break;
    int a[n];
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    printf("CASE# %d:\n",++count);
    sort(a+1,a+n+1);
    while(m--){
        int x;
        scanf("%d",&x);
        int flag=0;
        for(int i=1;i<=n;i++){
            if(x==a[i]){
                printf("%d found at %d\n",x,i);
                flag=1; 
                break;
            }
        }
        if(!flag) printf("%d not found\n",x);
    }
    }
     
    
    return 0;
}

posted @ 2019-02-20 10:26 芩溪兒閱讀(681) 評論(0) 收藏舉報

刷新頁面返回頂部

咕嚕咕嚕——干飯啦干飯啦

大理石在哪兒（Where is the Marble？，Uva 10474）

公告