C++ 改程序！ POJ 1002 http:⼀⼀poj.org⼀problem?id=1002 谁能帮我改一下程序！！！

你使用的是快速排序算法，它并不是一个稳定的排序算法，在有的情况下，它会退化为O(n^2)的时间复杂度，这题n的最大值为100000，可能达到O(n^2)的算法在2s的时间限制下，就显得有点不合适了，建议使用较为稳定的一些排序算法，如合并排序等等，代码如下：
#include
#include
#include

int readline(){
int num=0,i,t,len;
char a[50];
int b[26]=;
scanf("%s",a);
for(i=0,len=strlen(a);i if(a[i]!='-'){
if(a[i]<'A') t=a[i]-48;
else t=b[a[i]-'A'];
num=10*num+t;
}
}
return num;
}
struct MergeSort {
void merge(int array[], int p, int q, int r)
{
int i,k;
int begin1,end1,begin2,end2;
int* temp = (int*)malloc((r-p+1)*sizeof(int));
begin1= p;
end1 = q;
begin2 = q+1;
end2 = r;
k = 0;
while((begin1 <= end1)&&( begin2 <= end2))
{
if(array[begin1] < array[begin2])
{
temp[k] = array[begin1];
begin1++;
}
else
{
temp[k] = array[begin2];
begin2++;
}
k++;
}
while(begin1<=end1)
{
temp[k++] = array[begin1++];
}
while(begin2<=end2)
{
temp[k++] = array[begin2++];
}
for (i = 0; i <= (r - p); i++)
array[p+i] = temp[i];
free(temp);
}
void mergeSort(int array[], int first, int last)
{
int mid = 0;
if(first {
mid = (first+last)/2;
mergeSort(array, first, mid);
mergeSort(array, mid+1,last);
merge(array,first,mid,last);
}
}
} sortIt;
int main(){
int i,j,n,t1,t2,flag,*array;
scanf("%d",&n);
array=(int *)malloc(n*sizeof(int));
for(i=0;i array[i]=readline();
}
sortIt.mergeSort(array, 0, n - 1);
for(i=0,j=1,flag=0;i while(array[i]==array[i+1]){
i++;
j++;
}
if(j>1){
t1=array[i]/10000;
t2=array[i]-t1*10000;
printf("%03d-%04d %d\n",t1,t2,j);
flag=1;
j=1;
}
i++;
}
if(flag==0) printf("No duplicates.\n");
return 0;
}

#include
#include
#include
#include
using namespace std;
#define N 100005
char temp[10000];
//char map[N][20];
int map1[N];
int n;
int app[N];
int main()
{
memset(app,0,sizeof(app));
scanf("%d",&n);
for(int i=0;i scanf("%s",temp);
int t=0;
char q[10];
//printf("%d\n",strlen(temp));
for(int j=0;j //if(temp[j]=='-') continue;
if(temp[j]>='0'&&temp[j]<='9'){
q[t]=temp[j];
t++;
// continue;
}
if(temp[j]=='A'||temp[j]=='B'||temp[j]=='C'){
q[t]='2';
t++;
//continue;
}
if(temp[j]=='D'||temp[j]=='E'||temp[j]=='F'){
q[t]='3';
t++;
//continue;
}
if(temp[j]=='G'||temp[j]=='H'||temp[j]=='I'){
q[t]='4';
t++;
//continue;
}
if(temp[j]=='J'||temp[j]=='K'||temp[j]=='L'){
q[t]='5';
t++;
//continue;
}
if(temp[j]=='M'||temp[j]=='N'||temp[j]=='O'){
q[t]='6';
t++;
//continue;
}
if(temp[j]=='P'||temp[j]=='R'||temp[j]=='S'){
q[t]='7';
t++;
//continue;
}
if(temp[j]=='T'||temp[j]=='U'||temp[j]=='V'){
q[t]='8';
t++;
//continue;
}
if(temp[j]=='W'||temp[j]=='X'||temp[j]=='Y'){
q[t]='9';
t++;
//continue;
}
}
q[t] = 0;
map1[i]=atoi(q);
}

//for(int i=1;i<=n;i++)
// printf("*%s*\n",map[i]);
sort(map1,map1+n);
int h=0;
for(int i=0;i if(app[i]==0){
//printf("%s\n",map[i]);
int ans=1;
app[i]=1;
int j;
for(j=i+1;j if(map1[i]==map1[j]&&app[j]==0){
//printf("[%d]\n",j);
app[j]=1;
ans++;
}
else
break;
}
if(ans>1){
h=1;
char ad[10];
sprintf(ad,"%07d",map1[i]);
for(int k=0;k printf("%c",ad[k]);
if(k==2) printf("-");
}
printf(" %d\n",ans);
}
i = j-1;
}
}
if(h==0) printf("No duplicates.\n");
//scanf("%*d");
return 0;
}

汗 那么长的代码都能通过 为啥我的这么短的都运行超时

/*
author: Weeky
e-mail: kissthefuture@live.cn
copyleft: GPL v3
2012-03-08
*/
#include
#include
#include
using namespace std;
int main(int argc, char *argv[])
{
string table("000000000000000000000000000000000000000000000000012345678900000002223334445556667077888999");
multiset digits;
set uniq_str;
int i = 0, max_num;
cin>>max_num;
while(i != max_num)
{
string input, trans;
cin>>input;
for(string::size_type index = 0; index != input.size(); ++index)
{
if (input[index] != '-') trans += table[input[index]];
}
digits.insert(trans);
++i;
}

uniq_str.insert(digits.begin(), digits.end());

i = 0;
for(set::iterator index = uniq_str.begin(); index != uniq_str.end(); ++index)
{
int times = digits.count(*index);
if (times > 1)
{
string t = *index;
string ouput_str;
for(string::size_type t_index = 0; t_index != t.size(); ++t_index)
{
if (t_index != 3) ouput_str += t[t_index];
else ouput_str = ouput_str + "-" + t[t_index];
}
cout << ouput_str << " " << times << endl;
i += 1;
}
}

if (i == 0) cout << "No duplicates.\n" < return 0;
}

每个for循环语句里int i的int去掉，然后在主函数开头添上int i; 因为这是用C语言写的，如果是用C++的话不用改动