贪心 poj3045

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 
 8 class node
 9 {
10 public:
11     long long w,s;
12     bool operator < (node n) const
13     {
14         return w+s<n.w+n.s;
15     }
16 }bn[50010];
17 
18 int main()
19 {
20     int n;
21     while(scanf("%d",&n)!=EOF)
22     {
23         for(int i=0;i<n;i++)
24             scanf("%I64d%I64d",&bn[i].w,&bn[i].s);
25         sort(bn,bn+n);
26         long long now=0;
27         long long ma=-bn[0].s;
28         for(int i=1;i<n;i++)
29         {
30             now+=bn[i-1].w;
31             if(now-bn[i].s>ma)
32                 ma=now-bn[i].s;
33         }
34         cout<<ma<<endl;
35     }
36     return 0;
37 }
View Code