NOJ 比赛成绩查询问题II hash

NOJ 比赛成绩查询问题II hash_map

比赛成绩查询问题II

时间限制(普通/Java) : 1000 MS/ 3000 MS 运行内存限制 : 81920 KByte
总提交 : 349 测试通过 : 41

题目描述

2014“华为杯”南京邮电大学大学生团体歌唱大赛参赛团队的队名由“2014nupthw”和顺序号组合而成，例如2014nupthw001、2014nupthw002、2014nupthw028、2014nupthw089等。大赛结束后，任何人都可以通过队名查询任何一支队伍的排名，同时也可以通过排名查询队名，这里队伍排名从1开始且无并列情况。主办方提供所有参赛团队队名和排名的对应列表以及需要咨询的参赛团队队名或排名，请你完成此次大赛的成绩查询工作。

输入

输入包括多个行：第1行给出参赛团体总数N、需要查询成绩的参赛团队数；接下来有N行，每一行先后给出参赛团体的队名和最终排名；接下来有M行，每一行给出需要查询排名的参赛团队的队名或者需要查询参赛团体队名的排名。这里1≤N<10000，1≤M≤1000000。

输出

对应输入中最后M行要查询排名的参赛团队的队名或者需要查询参赛团体队名的排名，输出M行，每一行给出要查询的相应参赛团队队名、排名，以一个空格分隔上述两项内容。

样例输入

4 3
2014nupthw089 2
2014nupthw028 1
2014nupthw001 4
2014nupthw002 3
2014nupthw002
2
2014nupthw028

样例输出

2014nupthw002 3
2014nupthw089 2
2014nupthw028 1

分析：这一题用map超时，用数组或者结构体就不用说了，更超时。

目前较好的解法就是使用哈希映射hash_map，对于查询输入队名的情况，我们直接使用哈希，对于查询输入排名的情况，我们额外定义了一个数组进行存储。当然也可以用反方向的hash_map，但是自己要写函数~

下面附上AC代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#include<ext/hash_map>
using namespace __gnu_cxx;
using namespace std;
int N,sn,a,b;
char tt[10000+1][16],s[16];
struct eqstr
{
    bool operator()(const int s1,const int s2) const  //判断函数
    {
       return s1==s2;
    }
};
int main()
{
    //freopen("data.in","r",stdin);   //打开数据文件
	scanf("%d%d",&N,&sn);
    hash_map<int,int,hash<int>,eqstr> mymap;
    memset(tt,'',sizeof(tt));
    getchar();
    for(int i=0;i<N;i++)
    {
        scanf("%s%d",&s,&b);
        a=atoi(s+10);  //atoi将字符串转化成整型数
        mymap[a]=b;
        strcpy(tt[b],s);
    }
    for(int i=0;i<sn;i++)
    {
        scanf("%s",&s);
        if(strlen(s)>=6){
            a=atoi(s+10);
            if(mymap.find(a)!=mymap.end())
                printf("%s %d
",s,mymap[a]);
        }
        else
        {
             a=atoi(s);
             printf("%s %d
",tt[a],a);
        }
    }
}