这题不难，但测试数据（http://www.ntnu.edu.tw/acm/ProblemSetArchive/B_US_EastCen/1999/index.html）很野蛮，有好几个是1百万行的测试数据。
一开始没注意到2000毫秒的限制，结果第一个版本的程序写成了许多函数，尽量避免全局变量，还用了动态内存分配和struct。后来发现总是超时。网上查了别人的解答，发现要过的话就必须做比较强的输入格式假设，然后不要管太多style的原则，尽量在一个main里完成。另外输入输出不要用流，流好像有点慢。
网上（http://www.cnblogs.com/mobileliker/archive/2013/05/26/3099748.html）的一个比较好的结构是直接开一个1千万的稀疏数组来存0-9999999的条形图计数，省去nlgn的排序。内存限制不紧，有65536KB，这个数组整形的话是4千万字节，大约35000K字节，所以内存够用。
这个解法另一个值得借鉴的地方是他读入的方式，他读入用的是一个字符一个字符地读，看上去很散漫，但确实节约了一次读一行再iterate每个字符的重复工作。i/o的效率是过的关键
我的解答是借鉴了上面这个办法的，和他的解法也比较像，说明确实这么写是push这个方法到比较极致的状态了。
#include "stdio.h"
int _n, _nodup = 0, _idx[10000000];
int _mapint[25] = {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};
int main(){
register int _i, _j, _x;
register int _k;
register char _c;
scanf("%d\n",&_n);
for(_i = 0; _i < _n; ++_i){
_x = 0; _j = 0;
while(_j < 7){
_c = getchar();
if(_c >= '0' && _c <= '9'){
_x = _x * 10 + _c - '0';
++_j;
}else if(_c >= 'A' && _c <= 'Y' && _c != 'Q'){
_x = _x * 10 + _mapint[_c - 'A'];
++_j;
}
}
_idx[_x]++;
while(getchar() != '\n');
}
for(_i = 0; _i < 10000000; ++_i){
_k = _idx[_i];
if(_k > 1){
printf("%03d-%04d %d\n", (_i/10000), (_i%10000), _k);
_nodup = 1;
}
}
if(_nodup == 0) printf("No duplicates.\n");
return 0;
}
int _n, _nodup = 0, _idx[10000000];
int _mapint[25] = {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};
int main(){
register int _i, _j, _x;
register int _k;
register char _c;
scanf("%d\n",&_n);
for(_i = 0; _i < _n; ++_i){
_x = 0; _j = 0;
while(_j < 7){
_c = getchar();
if(_c >= '0' && _c <= '9'){
_x = _x * 10 + _c - '0';
++_j;
}else if(_c >= 'A' && _c <= 'Y' && _c != 'Q'){
_x = _x * 10 + _mapint[_c - 'A'];
++_j;
}
}
_idx[_x]++;
while(getchar() != '\n');
}
for(_i = 0; _i < 10000000; ++_i){
_k = _idx[_i];
if(_k > 1){
printf("%03d-%04d %d\n", (_i/10000), (_i%10000), _k);
_nodup = 1;
}
}
if(_nodup == 0) printf("No duplicates.\n");
return 0;
}
编辑1： 也许进一步加速可以在回避输出部分取余数操作符"%"上进行。
