http://acm.hdu.edu.cn/showproblem.php?pid=2491
题目大意:一个牧师要主持n个婚礼,牧师参加每个婚礼的时间要大于婚礼总时间的一半,给出每个婚礼的起止时间,问能否安排牧师主持每一个婚礼。
思路:贪心思想。按每个婚礼的中间时间(即牧师离开该婚礼的最早时间)升序排序。如果中间时间相等,按开始时间升序排序。然后依次安排即可。
#include<iostream> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> using namespace std; struct node { int start,end,last,middle; }wedding[100005]; int cmp(const void* a,const void* b) { if((*(node*)a).middle == (*(node*)b).middle) return (*(node*)a).start-(*(node*)b).start; else return (*(node*)a).middle-(*(node*)b).middle; } int main() { int n,time,i; while(scanf("%d",&n),n){ for(i=0;i<n;i++){ scanf("%d%d",&wedding[i].start,&wedding[i].end); wedding[i].last=(wedding[i].end-wedding[i].start)/2+1;//仪式持续时间超过婚礼一半 wedding[i].middle=wedding[i].start+wedding[i].last; } qsort(wedding,n,sizeof(wedding[0]),cmp); time=wedding[0].start; for(i=0;i<n;i++){ if(time>wedding[i].end-wedding[i].last){ break; } if(time<=wedding[i].start) time=wedding[i].middle; else time+=wedding[i].last; } if(i==n) printf("YES\n"); else printf("NO\n"); } return 0; }