https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2329

　　很好的一道貪心題。在貪心的時候，因為時間安排是要連續的，所以用區間的中點作為排序的依據。中點靠前的區間要先貪心，標記當前最后的時間點。

View Code 1 #define REP(i, n) for (int i = 0; i < (n); i++) 2 3 struct Cerem { 4 int begin, end; 5 int len, mid; 6 Cerem(int b = 0, int e = 0) { 7 begin = b, end = e; 8 len = (e - b >> 1) + 1; 9 mid = b + len; 10 } 11 } cerem[N]; 12 13 bool cmp(Cerem a, Cerem b) { 14 return a.mid < b.mid; 15 } 16 17 void input(int n) { 18 int b, e; 19 REP(i, n) { 20 scanf("%d%d", &b, &e); 21 cerem[i] = Cerem(b, e); 22 } 23 sort(cerem, cerem + n, cmp); 24 } 25 26 bool work(int n) { 27 int end = 0; 28 REP(i, n) { 29 if (end <= cerem[i].begin) end = cerem[i].begin + cerem[i].len; 30 else if (end + cerem[i].len <= cerem[i].end) end += cerem[i].len; 31 else return false; 32 } 33 return true; 34 } 35 36 int main() { 37 int n; 38 while (~scanf("%d", &n) && n) { 39 input(n); 40 work(n) ? puts("YES") : puts("NO"); 41 } 42 return 0; 43 }

?

——written by Lyon

?

轉載于:https://www.cnblogs.com/LyonLys/archive/2013/03/03/LA_4328_Lyon.html

總結

以上是生活随笔為你收集整理的LA 4328 Priest John's Busiest Day (Greedy)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。