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

Time limit exceed!请高手指点,谢谢!

Posted by cccfff at 2005-03-24 20:27:43 on Problem 1002
#include <iostream.h>
#include <stdlib.h>

int ch();
void pr(int,int);
void quickSort(int *,int,int);
int partition(int *,int,int);
void swap(int&,int&);

int li=0;

void main()
{
	int tt;
	cin >>tt;
	char rr[2];
	cin.getline(rr,'\n');
	int *p=new int[tt];
	for(int i=0;i<tt;i++)
	{
		p[i]=ch();
	}
	quickSort(p,0,tt-1);
	for(int j=0;j<tt-1;)
	{
		int k=1;
		int ss=0;
		while(j+k<tt && p[j+k]==p[j])
		{
			ss++;
			k++;
		}
		if(ss>=1)
		{
			pr(p[j],ss+1);
			j=j+ss+1;
		}
		else
			j++;
	}
	if(li==0)
		cout <<"No duplicates." <<endl;
}

int ch()
{
	int s=0;
	int t=1000000;
	do
	{
		char x;
		x=cin.get();
		if(x=='\n')
			break;
		if(x=='A'||x=='B'||x=='C'||x=='2')
		{
			s=s+2*t;
			t=t/10;
		}
		if(x=='D'||x=='E'||x=='F'||x=='3')
		{
			s=s+3*t;
			t=t/10;
		}
		if(x=='G'||x=='H'||x=='I'||x=='4')
		{
			s=s+4*t;
			t=t/10;
		}			
		if(x=='J'||x=='K'||x=='L'||x=='5')
		{
			s=s+5*t;
			t=t/10;	
		}		
		if(x=='M'||x=='N'||x=='O'||x=='6')
		{
			s=s+6*t;
			t=t/10;	
		}	
		if(x=='P'||x=='R'||x=='S'||x=='7')
		{
			s=s+7*t;
			t=t/10;	
		}
		if(x=='T'||x=='U'||x=='V'||x=='8')
		{
			s=s+8*t;
			t=t/10;		
		}
		if(x=='W'||x=='X'||x=='Y'||x=='9')
		{
			s=s+9*t;
			t=t/10;		
		}
		if(x=='1')
		{
			s=s+t;
			t=t/10;	
		}
		if(x=='0')
		{
			t=t/10;
		}
	}while(1);
	return s;
}


void pr(int x,int y)
{
	li=1;
	int tt=1000000;
	for(int i=1;i<=3;i++)
	{
		cout <<x/tt;
		x=x%tt;
		tt/=10;
	}
	cout <<'-';
	for(int j=1;j<=4;j++)
	{
		cout <<x/tt;
		x=x%tt;
		tt/=10;
	}
	cout <<" " <<y <<endl;
}


void quickSort(int *p,int x,int y)
{
	int t=partition(p,x,y);
	if(y-x<=0)
		return;
	else
	{
		quickSort(p,x,t-1);
		quickSort(p,t+1,y);
	}
}

int partition(int *q,int x,int y)
{
	int start,final;
	start=x,final=y;
	while(start<final)
	{
		for(;final>start;final--)
		{
			if(q[start]>q[final])
			{
				swap(q[start],q[final]);
				break;
			}
		}
		for(;start<final;start++)
		{
			if(q[start]>q[final])
			{
				swap(q[start],q[final]);
				break;
			}
		}
	}
	return start;
}

void swap(int& a,int& b)
{
	int t;
	t=a;
	a=b;
	b=t;
}





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