紫薯P108 例题5-1

一、题意

若干组数据。
每组第一行n、q分别表示石头数和询问数。
之后列出n个石头分别代表的数字。
之后q次询问每次一个数x，要求你输出x在这个石头序列排列后的第几个（或者找不到）。

二、解析

排序后用lower_bound

三、代码

#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 10000 + 5;
int n, q, a[maxn], kase = 1;

int main() {
    while(cin >> n >> q && (n || q)) {
        for(int i = 0; i < n; i ++) cin >> a[i];
        sort(a, a + n);
        cout << "CASE# " << kase ++ << ":\n";
        while(q --) {
            int x;
            cin >> x;
            int idx = lower_bound(a, a + n, x) - a;
            if(idx == n || a[idx] != x) cout << x << " not found" << endl;
            else cout << x << " found at " << idx + 1 << endl;
        }
    }
}

四、归纳

  • lower_bound(start, end, x)是经常用到的函数，作用是在一个排列好的序列中用二分法找到第一个>=x的数字的指针或迭代器，找不到时返回end
  • 拓展: upper_bound类似，找到的是第一个>x的位置