题意
请参考《LRJ大礼包::白》第一章例题2
思路
大概是贪心。
只要交代了任务,部下自己就会给做完了,基于这样的题意我们就可以设计这样的一种贪心策略:优先考虑完成任务时间长的,这样交代完了之后就会有更多的时间可以一边交代任务一边有人完成任务,更有效率。
具体操作就是把完成任务时间从大到小排个序,然后顺着检查一遍。
这个策略的证明在白书上面有提供,大概的证明套路就是说明不用这个策略时得到的答案不会更优,在证明时分类讨论了两种情况。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> #include <map> #include <complex> using namespace std; int n; pair<int,int> task[1005]; bool cmp(pair<int,int> a,pair<int,int> b){ if(a.second == b.second){ return a.first < b.first; }else{ return a.second > b.second; } } int work(){ int bound = 0; int now = 0; for(int i = 1; i <= n; i++){ now += task[i].first; bound = max(now + task[i].second, bound); } return bound; } int main(){ int d = 0; while(scanf(" %d",&n) != EOF){ d++; if(!n){ break; } for(int i = 1; i <= n; i++){ scanf(" %d %d",&task[i].first,&task[i].second); } sort(task+1,task+1+n,cmp); printf("Case %d: %d\n",d,work()); } return 0; } |