纯模拟,STL中map的应用吧。。
这题的数据比较BT,stdio输入输出+map+nlogn的算法都会TLE。。。
恩,在这个连O(n)都会TLE的年代,nlogn神马的都是浮云了,poj连常数都要卡。。。
所以呢,需要在字符串处理那里优化下,把char变成int来比较,具体的就见code吧。。。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
const int strs[26]= {2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 0, 7, 7, 8, 8, 8, 9, 9, 9, 0};
int main()
{
int times;
scanf("%d", ×);
map<int, int> names;
while(times--)
{
char str[100];
int strnum = 0, i = 0, num= 0;
scanf("%s", str);
while ( strnum < 7)
{
while ('-' == str[i])
i++;
if (str[i] >= 'A' && str[i] < 'Z')
{
num=num*10+strs[str[i]-'A'];
}
else
{
num=num*10+(str[i]-'0');
}
i++;
strnum++;
}
names[num]++;
}
int out= 1;
map<int, int>::iterator point;
for ( point = names.begin(); point != names.end(); point++ )
{
if (point->second > 1)
{
out= 0;
printf("%03d-%04d %d\n", point->first/10000, point->first%10000, point->second);
}
}
if(out)
{
printf("No duplicates.\n");
}
return 0;
}