Question

北大poj1002题Time Limit Exceeded

#include<iostream>
#include<string>
using namespace std;
void change(string& str)
{
int j;
for(j=0;j<str.length();j++)
if(str[j]==45)
str.erase(j,1);
for(j=0;j<str.length();j++)
{
if((str[j]>=65)&&(str[j]<=67))
{
str[j]='2';
continue;
}
if((str[j]>=68)&&(str[j]<=70)){
str[j]='3';continue;
}
if((str[j]>=71)&&(str[j]<=73)){
str[j]='4';continue;
}
if((str[j]>=74)&&(str[j]<=76)){
str[j]='5';continue;
}
if((str[j]>=77)&&(str[j]<=79)){
str[j]='6';continue;
}
if((str[j]==80)||(str[j]==82)||(str[j]==83)){
str[j]='7';continue;
}
if((str[j]>=84)&&(str[j]<=86)){
str[j]='8';continue;
}
if((str[j]>=87)&&(str[j]<=89))
str[j]='9';
}
str.insert(3,"-");
}
int main()
{
int n,i,j,q=0,sign=0;
cin>>n;
int* num=new int[n];
for(i=0;i<n;i++)
num[i]=1;
string* s=new string[n];
for(i=0;i<n;i++)
{
cin>>s[i];
change(s[i]);
for(j=0;j<i;j++)
if(s[i]==s[j])
{
num[j]++;
i--;
n--;
sign=1;
}
}
if(sign==0)
{
cout<<"No duplicates.";
return 0;
}

string min;
int minum;
int ha;
for(i=0;i<n;i++)
if(num[i]==1)
s[i]="";
for(i=0;i<n;i++)
{min="aaa-aaaa";
minum=2;
sign=0;
for(j=0;j<n;j++)
{

if(s[j]!="")
{
if(min>s[j])
{
min=s[j];
minum=num[j];
ha=j;
sign=1;
}

}

}
if(sign==1)
{
cout<<min<<" "<<minum<<endl;
s[ha]="";
}
}

}

Answer 1

O(N^2) 必须超时
建议先排序