UVALive - 4328 Priest John's Busiest Day

题意:给你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;
}



UVALive - 4328 Priest John's Busiest Day

上一篇:Servlet通过get方式接受参数乱码解决方法


下一篇:浅谈Codeforces round 217 Summer Reading的两种解法:DP与构造