贪心
每个婚礼必须参加的时间超过一半
#include<stdio.h> #include<stdlib.h> #include<string.h> struct op { int st,md,ed,mt; }p[100010]; int cmp(const void *a,const void *b) { struct op *c,*d; c=(struct op *)a; d=(struct op *)b; return c->md-d->md; } int main() { int i,j,k,n,m; while(scanf("%d",&n),n>0) { for(i=0;i<n;i++) { scanf("%d%d",&p[i].st,&p[i].ed); p[i].mt=(p[i].ed-p[i].st)/2+1; p[i].md=p[i].st+p[i].mt; } qsort(p,n,sizeof(p[0]),cmp); int t=p[0].md;//参加上个婚礼结束的时间 for(i=1;i<n;i++) { if(p[i].ed-p[i].mt<t)//参加当前婚礼的时间不够一半时间 break; if(t>p[i].st) t+=p[i].mt;//如果参加婚礼时婚礼已开始,结束时间就加上婚礼一半的时间 else t=p[i].md;//婚礼没开始,结束时间就是婚礼的中间时刻 } if(i==n)puts("YES"); else puts("NO"); } return 0; }