怎么快速查找我要的资料呢(北邮ACM1003)

Input
输入数据分为名单和询问两部分。

首先是名单部分，第一行是一个正整数 n (n<=500000), 表示名单中的人数。下面 n 行, 每一行有一个由大写字母A-Z和小写字母a-z组成的字符串，代表名单中的姓名。

然后是询问部分，第一行是一个正整数 m (m<=10000), 表示询问的次数。下面 m 行, 每一行有一个由大写字母A-Z和小写字母a-z组成的字符串，代表要查询的姓名。


输入中的每个字符串长度不超过10。

Output
对于每一次查询，如果要查询的字符串出现在名单中输出 "YES", 否则输出 "NO"。(注意不要加引号)
每一次查询占一行。

Sample Input

5
abc
edfg
x
a
Mike
3
Mike
bc
EDFG

Sample Output

YES
NO
NO

#include <iostream>
using namespace std;

struct List{
    char    *name;            //名字

    int        value;            //哈希键值

};

int ELFhash(char *key)
{
    unsigned long h = 0;
    unsigned long g;
    while( *key )
    {
        h =( h<< 4) + *key++;
        g = h & 0xf0000000L;
        if( g ) h ^= g >> 24;
        h &= ~g;
    }
    return h;
}

static List    *list;                            //名单

static List    *query;                            //查询列表


int cmp(const void *a, const void *b){
    return list[*(int *)a].value >= list[*(int *)b].value ? 1 : -1;
}

int main(){            //1003

    int num_list = 0, num_query = 0;        //名单数，查询数

    scanf("%d", &num_list);

    int *pIndex = new int[num_list];        //pList为索引列表

    list = new List[num_list];                //建立一级索引列表(哈希表)

    int i = 0, j = 0, k = 0;
    for(i = 0; i < num_list; i++){            //读取名单，并建立一级哈希表

        list[i].name = (char *)malloc( sizeof(char) * 11 );
        scanf("%s", list[i].name);

        pIndex[i] = i;
        //计算哈希键值

        list[i].value = ELFhash(list[i].name);
    }
    qsort(pIndex, num_list, sizeof(int), cmp);

    scanf("%d", &num_query);
    query = new List[num_query];                    //确定查询列表里姓名数量

    for(i = 0; i < num_query; i++){                    //确定查询列表

        query[i].name = (char *)malloc( sizeof(char) * 11 );
        scanf("%s", query[i].name);
        //计算哈希键值

        query[i].value = ELFhash(query[i].name);
    }
    
    int low = 0, high = 0;
    int mid = 0;
    bool isFind = false;
    for(k = 0; k < num_query; k++){
        isFind = false;
        low = 0;
        high = num_list - 1;
        while(low <= high){
            mid = (low + high) / 2;
            if(list[ pIndex[mid] ].value == query[k].value){
                //这里要解决哈希表里的冲突，因为可能出现同等权值排在一块，须向前追溯到相等权值的首个名字

                i = 0;        //须向前追溯的步数

                j = mid;
                while( j > 0 && list[ pIndex[j-1] ].value == query[k].value){
                    i++;
                    j--;
                }
                for(j = mid - i; j < num_list && list[ pIndex[j] ].value == query[k].value; j++)
                    if(strcmp( list[ pIndex[j] ].name , query[k].name ) == 0)
                    {
                        isFind = true;            //名单上有该名字

                        break;
                    }
                break;
            }
            else if(list[ pIndex[mid] ].value > query[k].value){
                high = mid - 1;
            }
            else{
                low = mid + 1;
            }
        }
        if(isFind)
            printf("YES\n");
        else                                //名单上没有该名字

            printf("NO\n");
    }


    return 0;
}