Question

请教北大ACM1002题目超时问题

Description

企业喜欢用容易被记住的电话号码。让电话号码容易被记住的一个办法是将它写成一个容易记住的单词或者短语。例如，你需要给滑铁卢大学打电话时，可以拨打TUT-GLOP。有时，只将电话号码中部分数字拼写成单词。当你晚上回到酒店，可以通过拨打310-GINO来向Gino's订一份pizza。让电话号码容易被记住的另一个办法是以一种好记的方式对号码的数字进行分组。通过拨打必胜客的“三个十”号码3-10-10-10，你可以从他们那里订pizza。

电话号码的标准格式是七位十进制数，并在第三、第四位数字之间有一个连接符。电话拨号盘提供了从字母到数字的映射，映射关系如下：
A, B, 和C 映射到 2
D, E, 和F 映射到 3
G, H, 和I 映射到 4
J, K, 和L 映射到 5
M, N, 和O 映射到 6
P, R, 和S 映射到 7
T, U, 和V 映射到 8
W, X, 和Y 映射到 9
Q和Z没有映射到任何数字，连字符不需要拨号，可以任意添加和删除。 TUT-GLOP的标准格式是888-4567，310-GINO的标准格式是310-4466，3-10-10-10的标准格式是310-1010。
如果两个号码有相同的标准格式，那么他们就是等同的（相同的拨号）
你的公司正在为本地的公司编写一个电话号码薄。作为质量控制的一部分，你想要检查是否有两个和多个公司拥有相同的电话号码。
输入
12
4873279
ITS-EASY
888-4567
3-10-10-10
888-GLOP
TUT-GLOP
967-11-11
310-GINO
F101010
888-1200
-4-8-7-3-2-7-9-
487-3279
输出
310-1010 2
487-3279 4
888-4567 3
我的程序
var n,i,j,k,x:longint;
s:string;
a:array[1..100000] of string;
new:array[1..1001] of string;
w:array[1..1001] of longint;
procedure change(var s:string);
var i,j,k,l:longint;
s1,s2:string;
begin
l:=length(s);
s1:='';
i:=1;
while i<=l do
begin
if (i=4)and(s[i]<>'-') then
begin
s1:=s1+'-';
s2:='-';
insert(s2,s,4);
inc(i);
inc(l);
end
else
begin
case s[i] of
'A','B','C':s1:=s1+'2';
'D','E','F':s1:=s1+'3';
'G','H','I':s1:=s1+'4';
'J','K','L':s1:=s1+'5';
'M','N','O':s1:=s1+'6';
'P','R','S':s1:=s1+'7';
'T','U','V':s1:=s1+'8';
'W','X','Y':s1:=s1+'9';
'1','2','3','4','5','6','7','8','9','0':s1:=s1+s[i];
'-':if i=4 then s1:=s1+s[i]
end;
if ((i<>4)and(s[i]='-'))then
begin
delete(s,i,1);
dec(l);
end
else
inc(i);
end;
end;
s:=s1;
end;
begin
readln(n);
for i:=1 to n do
begin
readln(s);
change(s);
a[i]:=s;
end;
x:=0;
for i:=1 to n do
begin
s:=a[i];
if s<>'' then
begin
k:=0;
for j:=1 to n do
if s=a[j] then
begin
inc(k);
a[j]:='';
end;
if k<>1 then
begin
inc(x);
new[x]:=s;
w[x]:=k;
end;
end;
end;
for i:=1 to x-1 do
for j:=i+1 to x do
begin
if new[i]>new[j] then
begin
s:=new[i];
new[i]:=new[j];
new[j]:=s;
k:=w[i];
w[i]:=w[j];
w[j]:=k;
end;
end;
if x=0 then writeln('No duplicates.')
else
for i:=1 to x do
writeln(new[i],' ',w[i]);
end.
一楼，我用快排还是超时~~
二楼，我是PASCAL编程，不是C++~~~

Answer 1

我记得这题要用快排的。。。反正排序需要nlogn的复杂度

我pascal很久没有用了...看不太懂，不过我说一下具体怎么写程序吧

首先读入的时候把所有的字串都改变成标准串。其实你不必对‘－’太多考虑，只须把所有串都改成标准数字串就可以了。比如310－1010就改成3101010，反正输出的时候‘－’可以单独拿出来输出，当然你觉得怎样方便怎样弄

然后对所有数串进行快排，你可否把你用快排的程序发上来，应该不会再有超时问题了啊

Answer 2

#include<iostream.h>
#include<iomanip.h>
#include<stdlib.h>

int compare(const void * a,const void * b)
{
return *((int*)a)-*((int*)b);
}

void main ()
{
int i,j,k,num,cal,value=1; cin>>num;
char a[100],b[8];//存char串的数组，多申一个位置比较好
//对于转化的问题，可以查表，比switch好
const char con[]="22233344455566677778889999";//QZ不会被输入，所以这样一起处理没问题7777
int * c=new int[num];//用动态内存分配不会浪费资源的，包括时间复杂度
for(i=0;i<num;i++)
{
cin>>a; k=0;
for(j=0;a[j];j++)
{
if(a[j]>='A' && a[j]<='Z')
{b[k]=con[a[j]-'A'];k++;continue;}
if(a[j]>='0' && a[j]<='9')
{b[k]=a[j];k++;}
}
//换成int进行排序//就算首位是零，这样也正确，因为首零，数字本来就小
c[i]=atoi(b);
}

qsort(c,num,sizeof(int),compare);

for(i=0;i<num;)
{
cal=1;
for(j=i+1;j<num&&c[j]==c[i];j++) cal++;//利用排好序的特点，把边算边输做到了极致
if(cal>1)
{
value=0;
cout<<setfill('0')<<setw(3)<<c[i]/10000<<"-"<<setfill('0')<<setw(4)<<c[i]%10000<<" "<<cal<<endl;//
}//setfill的使用，很好的解决了首位为零的问题
i=j;
}
if(value) cout<<"No duplicates."<<endl;
delete[]c;
}