| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1190 人关注过本帖, 1 人收藏
标题:map和字符型数组的问题
只看楼主 加入收藏
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:0 
以下是引用manesol在2013-8-10 13:45:25的发言:

做acm题目,翻译一个句子,要输入大量数据,所以要使用scanf输入,否则超时,所以不能用string类型而要使用字符数组,但是这些单词又要存到map中,所以我想知道字符数组到底怎么存到map中。
 
链接: http://acm.hdu.

我随手写了一个,能在VC9.0和g++4.8.1下编译通过,你看着再改改
程序代码:
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;

struct foo_item
{
    char english[11];
    unsigned long long martian; // 将字符串转换为数值比较的话,速度肯定比strcmp快多了

    foo_item( const char eng[11], const char mar[11] )
    {
        memcpy( english, eng, sizeof(english) );

        martian = 0;
        for( const char* p=mar; *p; ++p )
            martian = martian*26 + (*p-'a');
    }

    bool operator< ( const foo_item& rhs ) const
    {
        return martian < rhs.martian;
    }
};

struct foo
{
    std::vector<foo_item> english_martian;

    foo( size_t reserve_size )
    {
        english_martian.reserve( reserve_size );
    }
    void insert( const char eng[11], const char mar[11] )
    {
        english_martian.push_back( foo_item(eng,mar) );
    }
    void sort()
    {
        std::sort( english_martian.begin(), english_martian.end() );
    }
    const char* find( const char* mar_begin, const char* mar_end ) const
    {
        if( mar_end-mar_begin > 10 )
            return NULL;

        foo_item tmp( "", "" );
        tmp.martian = 0;
        for( const char* p=mar_begin; p!=mar_end; ++p )
            tmp.martian = tmp.martian*26 + (*p-'a');

        std::vector<foo_item>::const_iterator itor = std::lower_bound( english_martian.begin(), english_martian.end(), tmp );
        if( itor==english_martian.end() || tmp<*itor )
            return NULL;

        return itor->english;
    }
};

int main()
{
    // 读入字典表
    foo f( 1000 ); // 1000是瞎猜的,文中没提到字典大约有多少行。设正确了能提高效率,但不设也没关系
    {
        scanf( "%*s" ); // 忽略起始的START
        for( char english[11], martian[11]; scanf("%s%s",english,martian), english[0]!='E'; )
            f.insert( english, martian );
        f.sort();
    }

    // 读取martian文,并翻译
    scanf( "%*c" ); // 忽略
    for( char line[3001]; fgets(line,3000,stdin), strcmp(line,"END\n")!=0; )
    {
        for( const char* p=line; *p; )
        {
            if( *p<'a' || *p>'z' )
            {
                putchar( *p );
                ++p;
                continue;
            }

            const char* p1 = p;
            for( ++p; *p && *p>='a' && *p<='z'; ++p );

            const char* str = f.find( p1, p );
            if( str )
                printf( "%s", str );
            else
                printf( "%.*s", size_t(p-p1), p1 );
        }
    }

    return 0;
}

2013-08-10 15:59
manesol
Rank: 1
等 级:新手上路
帖 子:53
专家分:0
注 册:2013-7-6
收藏
得分:0 
回复 11楼 rjsp
辛苦了,虽然ac不了

[ 本帖最后由 manesol 于 2013-8-10 16:40 编辑 ]
2013-08-10 16:32
manesol
Rank: 1
等 级:新手上路
帖 子:53
专家分:0
注 册:2013-7-6
收藏
得分:0 
回复 11楼 rjsp
vector在查找效率上可以吗?会不会太慢了,map都不行
2013-08-10 19:26
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:528
帖 子:9024
专家分:54030
注 册:2011-1-18
收藏
得分:20 
以下是引用manesol在2013-8-10 16:32:41的发言:

辛苦了,虽然ac不了
我不会AC,我不知道AC的那些道道框框,我检查了一下代码
char line[3001]; fgets(line,3000,stdin),
应该是
char line[3002]; fgets(line,3002,stdin),
其它的错误我也看不出来。

“vector在查找效率上可以吗?会不会太慢了,map都不行 ” --- 这个,我听不懂,也回答不了你。但如果你还想更快,可以分段查询
比如建676个段,第一个段存aa开头的火星文,第二个段存ab开头的火星文,……最后一个段存zz开头的火星文。
2013-08-12 09:03
快速回复:map和字符型数组的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.015424 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved