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 chenxuan123456789 at 2012-09-16 10:02:02 on Problem 1089
#include <stdio.h>
#include <stdlib.h>
#define len 1000010
typedef struct node
{
	int s;
	int e;
}Node;
Node p[len];
int cmp(const void *_a,const void *_b)
{
	Node *a=(Node*)_a;
	Node *b=(Node*)_b;
	if(a->s==b->s)
	return b->e-a->e;
	return a->s-b->s;
}
int main()
{
	int n,i,j,m,k,t,flag;
	while(scanf("%d",&n)!=EOF)
	{
		for(i=0;i<n;i++)
		scanf("%d %d",&p[i].s,&p[i].e);
		qsort(p,n,sizeof(p[0]),cmp);
	     for(i=0;i<n;)
		{
			m=p[i].e;
			t=p[i].s;
			flag=0;
			for(j=i+1;j<n;j++)
			if(p[j].s>t&&p[j].s<=m)
			{
				t=p[j].s;
				if(p[j].e>m)
				{
					m=p[j].e;
					k=j;
					flag=1;
				}
			}
			if(flag)
			{
			
				printf("%d %d\n",p[i].s,m);
				i=k+1;
			}
			else
			{
				if(j!=i+1)
				{
				printf("%d %d\n",p[i].s,p[i].e);
				i++;
				}
			}
		}
	}
	return 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