问题描述

关于北大在线测试系统(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 %dn", TelTable[i] / 10000, TelTable[i] - TelTable[i] /10000 * 10000, Frequency);
            Frequency = 1;
            have_result = 1;
        }
    }
}
if (Frequency >= 2)
{
    printf ("%03ld-%04ld %dn", TelTable[i] / 10000, TelTable[i] - TelTable[i] /10000 * 10000, Frequency);
    Frequency = 1;
    have_result = 1;
}
if (have_result == 0)
{
    printf ("No duplicates.");
}
return 0;

}