【題解】UVa 10474 【Where is the Marble?】

这是一篇使用STL的题解,主要利用了三个函数:sort(),binary_search(),lower_bound()

sort():排序,,,我不想解释

binary_search():顾名思义,二分查找,不过这个函数有个很TD的问题,它的返回值是bool类型的,且前提是有序的容器。

下面是它的描述:“binary_search试图在已排序的[first, last)中寻找元素value。如果[first, last)内有等价于value的元素,它会返回true,否则返回false,它不返回查找位置”

这时就需要配合它的兄(er)弟(zi)函数:

lower_bound():
“lower_bound()它试图在已排序的[first,last)中寻找元素value。如果[first, last)具有等价于value的元素,lower_bound返回一个iterator指向其中第一个元素。如果没有这样的元素存在,它便返回假设这样的元素存在的话,会出现的位置”

人话便是:“指向第一个不小于value的元素。如果value大于[first, last)的任何一个元素,则返回last”

题目大意就是给你很多组测试,每组测试会包含一个大理石数组,和大理石的个数,还有询问的数字的数组和询问的次数。

你要做的便是,回答这所有测试的所有询问,它就问你那个数是否在排好序的大理石上,并打印下标

下面便是代码:

#include<cstdio>
#include<algorithm>

//解题函数
void solve(int n,int k){
    //如果没有大理石,即到达结束符,直接return
    if(n == 0){
        return;
    }

    const int L = 10000 + 6;//常量好改

    int nums[L] = {};//大理石
    int ques[L] = {};//询问

    //输入
    for(int i = 0;i < n;i++){
        scanf("%d",&nums[i]);
    }

    //输入x2
    for(int i = 0;i < k;i++){
        scanf("%d",&ques[i]);
    }

    std::sort(nums,nums + n);//给大理石排序

    //开始搜索
    for(int i = 0;i < k;i++){
        //如果搜得到
        if(std::binary_search(nums,nums + n,ques[i])){
            int pos = std::lower_bound(nums,nums + n,ques[i]) - nums;//记录位置,注意:这个函数(对于数组)返回的是那个数的指针,你要减掉数组的指针,才能得到int,不减不给编译,差评
            printf("%d found at %d\n",ques[i],pos + 1);//输出
        }else{
            printf("%d not found\n",ques[i]);//搜不到就说搜不到
        }
    }
}

int main(){
    int n,k,Case = 1;//n -> num of numbers;k -> num of questions
    while(scanf("%d %d",&n,&k) == 2 && n){//利用了scanf()的返回值,它返回输入的个数
        printf("CASE# %d:\n",Case++);
        solve(n,k);
    }

    return 0;
}