| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
居然超时了!求优化!各位大牛回答!#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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator