首页 > 代码库 > UVA1420 - Priest John's Busiest Day
UVA1420 - Priest John's Busiest Day
题目链接
题意:牧师John能否安排到所有婚礼,使其为所有婚礼送上祝福(祝福时间大于婚礼从时间的一半)。
思路:贪心,按照婚礼中间时间从小到大排序,尽量早结束婚礼祝福时间最晚开始(每个婚礼都有一个祝福时间最晚开始的时间)比较早的婚礼。
代码:
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 100005; struct wedding{ long long s, t, mid, l; }w[MAXN]; int n, flag; int cmp(wedding a, wedding b) { return a.mid < b.mid; } int solve() { int start = 0; for (int i = 0; i < n; i++) { if (start > w[i].t - w[i].l) return false; else if (start <= w[i].s) start = w[i].mid; else start += w[i].l; } return true; } int main() { while (scanf("%d", &n) && n) { for (int i = 0; i < n; i++) { scanf("%lld%lld", &w[i].s, &w[i].t); w[i].l = (w[i].t - w[i].s) / 2 + 1; w[i].mid = w[i].s + w[i].l; } sort(w, w + n, cmp); solve(); if (solve()) printf("YES\n"); else printf("NO\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。