11729 Commando War

贪心算法
 1 #include <iostream>
 2 #include <vector>
 3 #include <algorithm>
 4 
 5 using namespace std;
 6 
 7 struct Job{
 8     int j,b;
 9     bool operator < (const Job& x) const {
10         if( j == x.j ) return b < x.b;
11         return j > x.j;
12     }
13 };
14 
15 int main(){
16     int n,iCase = 0;
17     while( cin >> n && n ){
18         vector <Job> soldier(n);
19         for(int i = 0 ; i < n; i ++ ) cin >> soldier[i].b >> soldier[i].j;
20         sort(soldier.begin(),soldier.end());
21         int rightB = 0, ans  = 0;
22         for( int i = 0; i < n; i ++ ){
23             rightB += soldier[i].b;
24             ans = max(ans,rightB + soldier[i].j);
25         }
26         cout<<"Case "<<(++iCase)<<": "<<ans<<endl;
27     }
28     return 0;
29 }