POJ 2503 qsort+bsearch

题意很简单 就是给一个最多有100000对单词的英语和外语的字典 然后给你一个词 要求翻译
我开始受刚作的一个题的影响 建了一个树 然后查找 不过超时了 应该是建树的开销比较大吧
后来用的是排序然后二分查找 200+ms就过了 还是比较快的
cmp函数参考了http://185229677.itpub.net/
在此表示感谢
代码贴出来 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

struct dict
{
    char english[11];
    char foreign[11];
}a[100001];

int mycmp(const void * aa,const void *b)
{
    return strcmp(((dict*)aa)->foreign,((dict*)b)->foreign);
}

int cmp(const void* aa,const void* b)
{
    return strcmp((char*)aa,((dict*)b)->foreign);
}

int main()
{
    char line[30],query[11];
    int i=0,j,k;
    while(gets(line))
    {
        if(!strcmp(line,"")) break;
        k=strlen(line);
        for(j=0;j<k;j++)
        {
            if(line[j]==' ')
            {
                line[j]='\0';
                break;
            }
        }
        strcpy(a[++i].english,line);
        strcpy(a[i].foreign,line+j+1);
    }

    qsort(a+1,i,sizeof(dict),mycmp);

    while(gets(query))
    {
        dict* f=(dict *)bsearch(query,a+1,i,sizeof(dict),cmp);
        if(f) printf("%s\n",f->english);
        else puts("eh");
    }
}


posted on 2008-08-18 10:26 Victordu 阅读(2090) 评论(9)  编辑 收藏 引用

评论

# re: POJ 2503 qsort+bsearch[未登录] 2008-08-18 14:27 ngn999

直接用map的话会tle!  回复  更多评论   

# re: POJ 2503 qsort+bsearch 2008-08-18 15:28 Victordu

@ngn999
- -!可能吧 STL还是要有选择的用  回复  更多评论   

# re: POJ 2503 qsort+bsearch 2008-08-18 16:44 沈臻豪(foxtail)

能用就用 不能用拉倒@Victordu
  回复  更多评论   

# re: POJ 2503 qsort+bsearch 2008-08-19 10:16 hsen

用md5求出字符串的key,然后用hashmap<md5, std::string>就行了。  回复  更多评论   

# re: POJ 2503 qsort+bsearch 2008-08-19 10:32 Victordu

@hsen
恩 可是那样时间开销要大  回复  更多评论   

# re: POJ 2503 qsort+bsearch 2008-08-21 15:47 hsen

其实md5的时间开销要比排序要小,因为md5算出来的key是定长的,只有8个字节,而且构造hashmap的速度在读入时就构造好了。
  回复  更多评论   

# re: POJ 2503 qsort+bsearch[未登录] 2008-08-24 12:59 Victordu

@Victordu
哦 开始没看仔细 谢谢了 ^_^  回复  更多评论   

# re: POJ 2503 qsort+bsearch 2008-09-18 10:02 amw

bsearch函数真的很有用,不用的话就是TLE  回复  更多评论   

# re: POJ 2503 qsort+bsearch 2009-03-06 17:22 rainyday

非常感谢你提供的代码!!!让我这个菜鸟终于找到了自己的错误...和理解了一些用法!!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


导航

<2008年8月>
272829303112
3456789
10111213141516
17181920212223
24252627282930
31123456

统计

常用链接

留言簿(5)

随笔档案(46)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜