2 clannad wawa CLANNAD_WAWA 于 2014.06.05 16:07 提问

关于北大在线测试系统(POJ)第1002题

晚辈前不久迷上了POJ,目前已经实现了这题(第1002题),并且优化到了188ms,希望高手能告知进一步优化的方法,我希望能进入100ms以内,多谢前辈们指点!

目前我已经知道性能瓶颈是fgets()这个函数上,它大概花了和排序相同的时间
scanf(),gets()我都试过了,效率没有fgets()高
而fread()在读取stdin的时候又没办法及时地跳出来,所以没法使用
(比如说,用fread从一个只有1000字节的文件中读取10000个字节,那么在读到文件尾后会自动地跳出来。而在读stdin的时候,并不存在所谓的文件尾,它以为你还要不停地输入下去)
排序我这里用的是STL里的sort()函数,应该是非常高效的。

附上代码:

#include
#include
#include
#include

int main (int argc, char * argv[])
{
int n;
char TelTemp[50];
int TelTable[100000];
int i;
int j;

char symbol_table[100];

int Frequency = 1;  
int have_result = 0;

symbol_table['0'] = 0;
symbol_table['1'] = 1;
symbol_table['A'] = symbol_table['B'] = symbol_table['C'] = symbol_table['2'] = 2;
symbol_table['D'] = symbol_table['E'] = symbol_table['F'] = symbol_table['3'] = 3;
symbol_table['G'] = symbol_table['H'] = symbol_table['I'] = symbol_table['4'] = 4;
symbol_table['J'] = symbol_table['K'] = symbol_table['L'] = symbol_table['5'] = 5;
symbol_table['M'] = symbol_table['N'] = symbol_table['O'] = symbol_table['6'] = 6;
symbol_table['P'] = symbol_table['R'] = symbol_table['S'] = symbol_table['7'] = 7;
symbol_table['T'] = symbol_table['U'] = symbol_table['V'] = symbol_table['8'] = 8;
symbol_table['W'] = symbol_table['X'] = symbol_table['Y'] = symbol_table['9'] = 9;

scanf ("%d", &n);
getchar();

for (i = 0; i < n; ++i)
{       
    int times = 6;  
    TelTable[i] = 0;


    fgets (TelTemp, 50, stdin);

    for (j = 0; j < 50; ++j)
    {   
        if (TelTemp[j] != '-')
        {               
            TelTable[i] = TelTable[i] * 10 + symbol_table[TelTemp[j]];
            --times;
            if (times < 0)
            {
                break;
            }
        }       
    }
}

std::sort (TelTable, TelTable + n);


for (i = 0; i < n - 1; ++i)
{
    if (TelTable[i] == TelTable[i + 1])
    {
        ++Frequency;
    }
    else
    {
        if (Frequency >= 2)
        {
            printf ("%03ld-%04ld %d\n", TelTable[i] / 10000, TelTable[i] - TelTable[i] /10000 * 10000, Frequency);
            Frequency = 1;
            have_result = 1;
        }
    }
}
if (Frequency >= 2)
{
    printf ("%03ld-%04ld %d\n", TelTable[i] / 10000, TelTable[i] - TelTable[i] /10000 * 10000, Frequency);
    Frequency = 1;
    have_result = 1;
}
if (have_result == 0)
{
    printf ("No duplicates.");
}
return 0;

}

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!