Where is the Marble? UVA – 10474

介绍：紫书stl入门习题

链接：https://cn.vjudge.net/problem/UVA-10474

题意：有n个大理石上标有数字，有q个问题，排序后回答每个问题数字的位置

解题思路：主要是考察对lower_bound和sort基本stl函数的使用

lower_bound:作用是查找大于或者等于x的一个位置

注意！返回的是地址而不是数组的下标或者其他什么，所以如果你需要得到下标可以这样：lower_bound(a,a+n,x)-a

sort:排序函数，原理类似于快排

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int  main()
{
    int n,q;//q是问题个数
    int cnt=0;
    while( cin>>n>>q&&n){
    int *a=(int *)malloc(sizeof(int)*n);//储存石头上的数字
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
    }
    //
    sort(a,a+n);//排序
    cout<<"CASE# "<<++cnt<<":"<<endl;
    int x;
    for(int i=0; i<q; i++)
    {
        cin>>x;
        int p= lower_bound(a,a+n,x)-a;
//要判断是否查找成功了
        a[p]==x?cout<<x<<" found at "<<lower_bound(a,a+n,x)-a+1<<endl:cout<<x<<" not found"<<endl;
    }
    free(a);
}
return 0;
}