晚辈前不久迷上了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;
}