UVA 10474 Where is the Marble?

UVA_10474

这个题目可以用Hash的思想，首先读入Marbles，进行排序，之后遍历一遍Marbles数组并给hash数组赋相应的值，其中hash[i]表示标号为i的Marble第一次出现的位置。

    之后每读入一个Q，只需要判断对应的hash数组中的元素是否被赋值，并进行相应的输出即可。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int a[10010],hash[10010];
int cmp(const void *_p,const void *_q)
{
    int *p=(int *)_p;
    int *q=(int *)_q;
    return *p-*q;
}
int main()
{
    int i,j,k,N,Q,t;
    t=0;
    while(1)
    {
        scanf("%d%d",&N,&Q);
        if(N==0)
            break;
        printf("CASE# %d:\n",++t);
        for(i=0;i<N;i++)
            scanf("%d",&a[i]);
        qsort(a,N,sizeof(a[0]),cmp);
        memset(hash,-1,sizeof(hash));
        for(i=0;i<N;i++)
            if(hash[a[i]]==-1)
                hash[a[i]]=i+1;
        for(i=0;i<Q;i++)
        {
            scanf("%d",&k);
            if(hash[k]==-1)
                printf("%d not found\n",k);
            else
                printf("%d found at %d\n",k,hash[k]);
        }
    }
    return 0;    
}