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

1002用了qsort后怎么还TLE啊,大大们给看看,谢谢了哈

Posted by allanlyy at 2005-04-22 12:30:44 on Problem 1002
#include <stdio.h>
#include <string.h>
#define MAX 100001
int sn[MAX];
char s[MAX][100];
int n,t;
struct T
{
	int data;
	int time;
}snt[MAX];

void Find()
{
	int i;
	t = -1;
	snt[0].data = 0;
	snt[0].time = 0;
	for(i = 0;i < n-1;i++)
	{
		if((i == 0)&&(sn[i] == sn[i+1]))
			{t++;snt[t].data = sn[i];snt[t].time = 2;}
		else if((sn[i] == sn[i+1])&&(sn[i - 1] != sn[i]))
			{t++;snt[t].data = sn[i];snt[t].time = 2;}
		else if(sn[i] == sn[i+1])
		{
			snt[t].time++;
		}
	}
	
}

int Sort(int low,int high)
{
	int k = sn[low];
	while(low < high)
	{
		while(low < high && sn[high] >= k)
			--high;
		sn[low] = sn[high];
		while(low < high && sn[low] <= k)
			++low;
		sn[high] = sn[low];
	}
	sn[low] = k;
	return low;
}

void Qsort(int low,int high)
{
	int key;
	if(low < high)
	{
		key = Sort(low,high);
		Qsort(low,key-1);
		Qsort(key+1,high);
	}
}
void Num()
{
	int i,j;
	for(i = 0;i < n;i++)
	{
		sn[i] = 0;
		for(j = 0;j < 7;j++)
		{
			if(j < 7)
			{
				sn[i] *= 10;
			}
			sn[i] = sn[i] + (s[i][j] - '0');
		}
	}
}

int main()
{
	char m[30] = "2223334445556667 77888999 ";
	int i,len,k,j,x,y;
	scanf("%d",&n);
	for(i = 0;i < n;i++)			//读数
	{
		scanf("%s",s[i]);
		len = strlen(s[i]);
		for(j = 0;j < len;j++)
		{
			while(s[i][j] == '-')
			{
				for(k = j;k < len - 1;k++)
				{
					s[i][k] = s[i][k+1];
				}
				s[i][k] = NULL;
			}
			if((s[i][j] >= 'A')&&(s[i][j] <= 'Z'))
			{
				s[i][j] = m[s[i][j] - 'A'];
			}
		}
	}
	Num();
	Qsort(0,n-1);
	Find();
	if(t == -1)
		printf("No duplicates.\n");
	else
	{
		for(i = 0;i <= t;i++)
		{
			if(snt[i].data/10000 > 99)x = 0;
			else if(snt[i].data/10000 > 9)x = 1;
			else x = 2;
			if(snt[i].data%10000 > 999)y = 0;
			else if(snt[i].data%10000 > 99)y = 1;
			else if(snt[i].data%10000 > 9)y = 2;
			else y = 3;
			for(j = 0;j < x;j++)
				printf("0");
			printf("%d-",snt[i].data/10000);
			for(j = 0;j < y;j++)
				printf("0");
			printf("%d",snt[i].data%10000);
			printf(" %d\n",snt[i].time);
		}
	}
	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