Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

高手帮看看,怎么TLE了?有什么办法改进,先谢谢了!!C++

Posted by wdjsj at 2009-07-30 15:46:51 on Problem 1002
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

void exchange(char*&a)
{

char* res = new char[8];
for(int i=0,j =0;i<(int)strlen(a);i++)
{ if(a[i]!='-') 
 {res[j]=a[i];j++;}
}
res[7] = '\0';
int m = 0,k = 0;
for(int i=0;i<7;i++)
{
	if(res[i]>='A'&&res[i]<='Z')
	{	m = res[i]-'A';
	    k = m/3;
	    if(m<=14)
		{ res[i] = k+2+'0';}
		else if(m>=15&&m!=16&&m<=18)
		{ res[i] = 7+'0';}
		else if(m>=19&&m<=21)
		{ res[i] = 8+'0';}
		else
		{ res[i] = 9+'0';}
	}
}
delete []a;
a = new char[8];
strcpy(a,res);
delete []res;

}
int split(char* x[],int first,int last)
{ 
	int split_point;
	char* pivot = new char[strlen(x[first])+1];
	strcpy(pivot,x[first]);
	split_point = first;
	for (int unknown = first +1;unknown <=last; unknown++)
		if (strcmp(x[unknown],pivot)<0)
		{  split_point++;
	       char* t= x[split_point];
		   x[split_point] = x[unknown];
		   x[unknown] = t;
	    }
	 x[first] = x[split_point];
	 x[split_point] = pivot;
	 return split_point;
}
void quick_sort( char* x[],int first,int last)
{ if(first<last)
{ int split_point;
  split_point = split(x,first,last);
  quick_sort(x,first,split_point-1);
  quick_sort(x,split_point+1,last);
}
}

int main()
{

int sum;
cin>>sum;
char** arr = new char*[sum];
int i = 0;
for( i=0;i<sum;i++)
{ arr[i] = new char[100];
  cin>>arr[i];
  exchange(arr[i]);
}

//计算循环次数
int* num = new int[sum];
for(i = 0;i<sum;i++)
num[i] = 1;
int j =0;
for(i =0;i<sum;i++)
{  for(j=i+1;j<sum;j++)
  {    if(num[j]==1)
      {      if(strcmp(arr[i],arr[j])==0)
           {  num[i]++;
              num[j] = -1;
           } 
      }
  }
} 
int k = 0;
for(i = 0;i<sum;i++)
{ if(num[i]>1) k++;
}
char** result = new char*[k];
j = 0;
//
for(i=0;i<sum;i++)
{  
	if(num[i]>1) 
	{ result[j] = new char[9];
	  strcpy(result[j],arr[i]);
	  result[j][7] = num[i] + '0';
	  result[j][8] = '\0';
	  j++;
	}
}

//delete
delete []num;
for(i=0;i<sum;i++)
delete []arr[i];
delete []arr;

quick_sort( result,0,k-1);


if(k==0) 
{ cout<<"No duplicates."<<endl;
  for(i=0;i<k;i++)
  delete [](result[i]);
  delete []result;
  return -1;
}
else
{
	for(i=0;i<k;i++)
   {
	for(j=0;j<3;j++)
	{ cout<<result[i][j];}
	cout<<"-";
	for(j=3;j<7;j++)
	{ cout<<result[i][j];}
	cout<<" ";
	cout<<result[i][7]<<endl;
    
   } 
	for(i=0;i<k;i++)
    delete [](result[i]);
    delete []result;
    return 0;
} 

}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator