题目链接：uva 1420 - Priest John's Busiest Day
题目大意：有一个司仪，要主持n场婚礼，给出婚礼的起始时间和终止时间，每个婚礼需要超过一半的时间做为仪式，并且仪式不能终止。问说司仪能否主持n场婚礼。
解题思路：贪心，为了尽量主持多的婚礼，每场的仪式时间就一定要尽量短d=(t-s)/2+1,(因为必须大于一半，所以加1）。然后按照每场婚礼可以最早结束的时间排序s+d，（因为要满足所有的婚礼，所以尽量解决早点的仪式，腾出时间来给后面的婚礼），维护一个占用时间值即可。
队友的做法是将每场婚礼按照最晚结束的时间排序t-d，会比较好理解一点。
#include#include #include using namespace std; const int N = 100005; struct state { int s, t, d; }p[N]; int n; bool cmp(const state& a, const state& b) { return a.s + a.d < b.s + b.d; } void init() { for (int i = 0; i < n; i++) { scanf("%d%d", &p[i].s, &p[i].t); p[i].d = (p[i].t - p[i].s) / 2 + 1; } sort(p, p + n, cmp); } bool judge() { int tmp = 0; for (int i = 0; i < n; i++) { tmp = max(tmp, p[i].s) + p[i].d; if (tmp > p[i].t) return false; } return true; } int main() { while (scanf("%d", &n) == 1 && n) { init(); printf("%s\n", judge() "YES" : "NO"); } return 0; }