题目大意
小镇有n场婚礼在一天之内矩形，第i场婚礼的开始时间为Si，结束时间为Ti。在每一场婚礼中，有一个重要仪式，即牧师给予两位新人传达主的祝福。对于第i场婚礼，祝福仪式可以在[Si,Ti]中任何时候举行，但是必须超过总时间的一半以上。
小镇只有一位牧师，所有的祝福仪式都必须要他在场。同时，牧师必须在整数时刻开始或者结束祝福仪式，不过他可以在结束一场之后立刻开始另一场。
现在给你所有婚礼的信息，请问是否能够安排好一个祝福仪式的顺序，使得牧师能够给所有新人带去祝福。
思路
刚开始思路就错了，以为按照每场婚礼的开始时刻排序再模拟就行，后来想想完全不对，根本不是那么一回事。例如(1,1000)和(2,500)这两场婚礼，按照开始时刻贪心，那么结果无疑是NO。
正确的方式应该是按婚礼的祝福仪式的“最早的结束时刻t1”或“最晚开始时间t2”排序再模拟。为何如此？因不管从什么时候开始一个祝福仪式，祝福仪式总是包含时间段(t1,t2)，我们称(t1,t2)为公共时间段，一场婚礼对应一个公共时间段。若存在一个方案可使所有祝福仪式正常举行，那么所有公共时间段也一定都不会出现重合。也由此可得结论，祝福仪式的举行顺序一定与公共时间段的出现顺序相同。
当然，我们不必将公共时间段的开始和结束时刻都求出来，我们只需求出其中一个即可，再依此对婚礼进行排序，最后按顺序模拟婚礼祝福仪式的举行。若所有祝福仪式都能在时间范围内结束，则说明存在一个方案可使所有祝福仪式按时完成，反之不存在。
代码
#include<iostream>
#include<stdio.h>
using namespace std;
struct point
//将每场婚礼的信息封装在结构体中。
{
int start;
int end;
int mid;
//mid表示此婚礼的祝福仪式至少持续mid分钟。
}t[100000];
int n;
int cmp(const void* m,const void* n)
//给婚礼按祝福仪式最早的结束时刻排序。
{
return (*(point*)m).start+(*(point*)m).mid-(*(point*)n).start-(*(point*)n).mid;
//start+mid表示婚礼最早的结束时刻。
}
bool solved()
{
qsort(t,n,sizeof(t[0]),cmp);
long long now=0;
for(int i=0;i<n;i++)
{
now=now>t[i].start?now+t[i].mid:t[i].start+t[i].mid;
//now为当前祝福仪式的结束时间。
if(now>t[i].end)
//如果祝福仪式结束时间晚于婚礼结束时间。
return false;
}
return true;
}
int main()
{
while(scanf("%d",&n)&&n)
{
for(int i=0;i<n;i++)
{
scanf("%d%d",&t[i].start,&t[i].end);
t[i].mid=(t[i].end-t[i].start)/2+1;
//注意题干中的条件，祝福仪式至少要“大于”婚礼总时间的一半。
}
printf("%s\n",solved()?"YES":"NO");
}
}