题意:给你N个婚礼的举办时间,只有一个牧师,判断牧师能否参加所有的婚礼(牧师能在任何时间加到婚礼中,必须是整数时刻且参加婚礼的时间必须是有一半以上的时间)
思路:贪心处理,因为要参加一半以上的时间,那么中间时刻就是最快能结束这个婚礼的时刻,那么如果每个中间时刻都没有冲突的话,那么就至少这个是能够实现,那么我们开始判断,取一半是最低的可能
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 100000; struct point{ int start; int end; int mid; }arr[MAXN]; int n; int cmp(const void *a,const void *b){ return (*(point*)a).start+(*(point*)a).mid-(*(point*)b).start-(*(point*)b).mid; } int solve(){ qsort(arr,n,sizeof(arr[0]),cmp); long long ans = 0; for (int i = 0; i < n; i++){ ans = ans>arr[i].start ? ans+arr[i].mid : arr[i].start+arr[i].mid; if (ans > arr[i].end) return false; } return true; } int main(){ while (scanf("%d",&n) != EOF && n){ for (int i = 0; i < n; i++){ scanf("%d%d",&arr[i].start,&arr[i].end); arr[i].mid = (arr[i].end-arr[i].start)/2 + 1; } printf("%s\n",solve()?"YES":"NO"); } return 0; }