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 Exceeded

Posted by bengbenglong at 2008-02-15 08:48:06 on Problem 1002
我的思路是先将字符串转化为标准格式的字符串,然后转化为数字,存入电话本,将电话本中的电话号码排序后,输出结果。提交后总是Time Limit Exceeded,请教各位如何节省时间,谢谢。下面是源代码:
#include <stdio.h>
#include <string.h>

/*1~26->A~Z,Q&Z 没有对应*/
const char table[27]={' ','2','2','2','3','3','3','4','4','4','5','5','5','6','6','6','7',' ','7','7','8','8','8','9','9','9',' '};

char Scantable(char str)
{
	char c;
	c=str-0x30;
	if (0<=c&&c<=9) return str;	
	else if(c<0||(9<c&&c<0x10)||c==17+0x10||c>=26+0x10) return 0;	
	else return table[c-0x10];
}

void Sort(int numbers[], int left, int right)
{
	int pivot, l_hold, r_hold; 

	l_hold = left; 
	r_hold = right; 
	pivot = numbers[left]; 
	while (left < right) 
	{ 
		while ((numbers[right] >= pivot) && (left < right)) 
			right--; 
		if (left != right) 
		{ 
			numbers[left] = numbers[right]; 
			left++; 
		} 
		while ((numbers[left] <= pivot) && (left < right)) 
			left++; 
		if (left != right) 
		{ 
			numbers[right] = numbers[left]; 
			right--; 
		} 
	} 
	numbers[left] = pivot; 
	pivot = left; 
	left = l_hold; 
	right = r_hold; 
	if (left < pivot) 
	Sort(numbers, left, pivot-1); 
	if (right > pivot) 
	Sort(numbers, pivot+1, right); 
}

int main()
{
	
	int strnum,listnum=0,i,j,flag,len,numScr,telbook[100000],repnum;
	char strScr[40],*strp;
	
	scanf("%d",&strnum);
	for(i=0;i<strnum;i++)
	{
		scanf("%s",strScr);	
		len=strlen(strScr);
		numScr=0;
	/*转化为标准格式的字符串号码*/
		strp=strScr;	
		while(*strp!='\0')
		{
			*strp=Scantable(*strp);
			if(!*strp)
			{
				for(j=strp-strScr;j<=len;j++)
					strScr[j]=strScr[j+1];
				continue;
			}
			strp++;			
		}
		strScr[7]='\0';
		strp=strScr;

		
	/*将字符串号码转化为数字*/
		while(*strp!='\0')
		{
			numScr=10*numScr+(*strp-0x30);
			strp++;
		}


		telbook[i]=numScr;		//存入电话本

	}

	Sort(telbook,0,strnum-1);					//对电话本中号码排序快速排序

	/*输出结果*/
	repnum=0;
	for(i=0,flag=0;i<strnum;i++)
	{
		if(telbook[i]!=telbook[i+1])	
		{
			if(repnum)
				printf("%03d-%04d %d\n",telbook[i]/10000,telbook[i]%10000,repnum+1);
			repnum=0;
		}
		else
		{
			repnum++;
			flag=1;
		}
		
	}
	if(!flag) 	printf("No duplicates.\n");
	
	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