hdu 4070（贪心）2011福州网络赛

 1 /**************************************************
 2  * Author     : xiaohao Z
 3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
 4  * Last modified : 2014-04-06 12:54
 5  * Filename     : fuzhou_ol2.cpp
 6  * Description     : 
 7  * ************************************************/
 8 
 9 #include <iostream>
10 #include <cstdio>
11 #include <cstring>
12 #include <cstdlib>
13 #include <cmath>
14 #include <algorithm>
15 #include <queue>
16 #include <stack>
17 #include <vector>
18 #include <set>
19 #include <map>
20 #define MP(a, b) make_pair(a, b)
21 #define PB(a) push_back(a)
22 
23 using namespace std;
24 typedef long long ll;
25 typedef pair<int, int> pii;
26 typedef pair<unsigned int,unsigned int> puu;
27 typedef pair<int, double> pid;
28 typedef pair<ll, int> pli;
29 typedef pair<int, ll> pil;
30 
31 const int INF = 0x3f3f3f3f;
32 const double eps = 1E-6;
33 const int LEN = 100110;
34 int n, tag[LEN];
35 pii p[LEN];
36 
37 bool cmp(pii a, pii b){
38     if(a.second != b.second) return a.second > b.second;
39     else return a.first < b.first;
40 }
41 
42 int main()
43 {
44 //    freopen("in.txt", "r", stdin);
45 
46     int T, a, b, kase = 1;
47     scanf("%d", &T);
48     while(T--){
49         scanf("%d", &n);
50         for(int i=1; i<=n; i++){
51             scanf("%d%d", &a, &b);
52             p[i] = MP(a, b);
53         }
54         sort(p+1, p+n+1, cmp);
55         int ans = 0, tans[LEN], ltag = 1;
56         for(int i=1; i<=n; i++){
57             ans += p[i].first;
58             tans[i] = ans;
59         }
60         int tmax = 0;
61         for(int i=1; i<=n; i++){
62             tmax = max(p[i].second - (ans - tans[i]), tmax);
63         }
64         printf("Case %d: ", kase++);
65         printf("%d\n", tmax+ans);
66     }
67     return 0;
68 }