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

总是超时.大牛看看这个可以改进吗?

Posted by forceil at 2007-04-10 17:06:33 on Problem 1828
#include "iostream.h"
#include "stdio.h"
int temp[50000][2];
int total=0;
void Sort(int index,int len);
void main()
{
	while(cin>>total)
	{
		if(total==0)
			break;
		
		for(int i=0;i<total;i++)
		{
			scanf("%d%d",&temp[i][0],&temp[i][1]);
		}
		Sort(0,total);
		int X_max=0;
		int num=0;
		for(i=total-1;i>=0;i--)
		{
			if(temp[i][0]>X_max)
			{
				X_max=temp[i][0];
				num++;	
			}
		}
		cout<<num<<endl;
	}
}
void Sort(int index,int len)
{
	if(len==1)
		return;
	int p=index;
	int or=index;
	int i=0;
	for(i=index;i<index+len;i++)
	{
		if(temp[i][1]<temp[or][1])
		{
			int t=temp[p][1];
			int t0=temp[p][0];

			temp[p][1]=temp[i][1];
			temp[p][0]=temp[i][0];
			
			temp[i][1]=t;
			temp[i][0]=t0;
			if(or==p)
				or=i;
			p++;
		}
	}
	if(or!=p)
	{
		int t=temp[or][1];
		int t0=temp[or][0];

		temp[or][1]=temp[p][1];
		temp[or][0]=temp[p][0];

		temp[p][1]=t;
		temp[p][0]=t0;
	}
	if(p!=index)
	{
		Sort(index,p-index);
	}
	if(p!=(index+len-1))
	{
		Sort(p+1,index+len-p-1);
	}
}

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