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