Question

北大 acm 1002 time limit exceeded http://acm.pku.edu.cn/JudgeOnline/problem?id=1002

#include<iostream>
using namespace std;
int main()
{
int i,j;
char s,c;
int N;
cin>>N;
scanf("%c",&c);
char **phone;
phone= new char *[N];
for(i=0;i<N;i++)
{
phone[i]=new char[8];
int k=0;
scanf("%c",&s);
for(j=0;s!='\n';j++)
{
if(s=='-')
{
scanf("%c",&s);
continue;
}
else if(s=='A' || s=='B' || s=='C' || s=='2')
{
phone[i][k]='2';
k++;
}
else if(s=='D' || s=='E' || s=='F' || s=='3')
{
phone[i][k]='3';
k++;
}
else if(s=='G' || s=='H' || s=='I' || s=='4')
{
phone[i][k]='4';
k++;
}
else if(s=='J' || s=='k' || s=='L' || s=='5')
{
phone[i][k]='5';
k++;
}
else if(s=='M' || s=='N' || s=='O' || s=='6')
{
phone[i][k]='6';
k++;
}
else if(s=='P' || s=='R' || s=='S' || s=='7')
{
phone[i][k]='7';
k++;
}
else if(s=='T' || s=='U' || s=='V' || s=='8')
{
phone[i][k]='8';
k++;
}
else if(s=='W' || s=='X' || s=='Y' || s=='9')
{
phone[i][k]='9';
k++;
}
else
{
phone[i][k]=s;
k++;
}
scanf("%c",&s);
}
phone[i][k]='\0';
}
char temp[8];
for(i=1;i<N;i++)
{
for(j=i;j>0;j--)
{
if(strcmp(phone[j],phone[j-1])>0)
{
strcpy(temp,phone[j-1]);
strcpy(phone[j-1],phone[j]);
strcpy(phone[j],temp);

}
}
}
int **data;
data=new int *[N];
for(i=0;i<N;i++)
{
data[i]=new int[2];
data[i][0]=0;
data[i][1]=0;
}
int num_ph=0;
for(i=1;i<N;i++)
{
if(!strcmp(phone[i-1],phone[i]))
{
data[num_ph][1]++;
}
else
{
num_ph++;
data[num_ph][0]=i;
}
}
int t;
for(i=0;i<=num_ph;i++)
{
for(j=i+1;j>0;j--)
{
if(data[j][1]>data[j-1][1])
{
t=data[j-1][1];
data[j-1][1]=data[j][1];
data[j][1]=t;
t=data[j-1][0];
data[j-1][0]=data[j][0];
data[j][0]=t;
}
}
}
for(i=0;i<=num_ph;i++)
{
if(data[i][1]!=0)
{
for(j=0;j<3;j++)
cout<<phone[data[i][0]][j];
cout<<"-";
for(;j<7;j++)
cout<<phone[data[i][0]][j];
cout<<" "<<data[i][1]+1<<endl;
}
}
for(i=0;i<N;i++)
{
delete []phone[i];
delete []data[i];
}
delete []phone;
delete []data;
return 0;
}
把cin,cout改成scanf,printf还是exceeded，我知道我的循环语句挺多，但是不知道再怎样化简或是换别的方法，希望高手帮帮忙，提供简单的办法。

Answer 1

具体怎么做我不太明白，针对你的代码我提两点建议：
1. 做ACM题目时，空间尽量用采用静态分配，比如定义为phone[1000][8]，别用动态分配new，这个很耗时的，并且最后的delete也要花费时间。
2. 对phone的赋值可以采用更高效的方法，分析一下赋值的规律，你可以这样：
scanf("%c",&s);
for(j=0;s!='\n';j++)
{
if(s=='-')
{
scanf("%c",&s);
continue;
}
if(s >= '0' && s <= '9')
phone[i][k] = s;
else if(s >= 'A' && s <= 'P')
phone = '0' + ((s - 'A') / 3) + 2;
else if(s >= 'R' && s <= 'Y')
phone = '0' + ((s - 'Q') / 3) + 2;
else
phone[i][k] = s;
k ++;
scanf("%c",&s);
}