HDU 4296 Buildings

按si+wi的和排序贪心即可
 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstdlib>
 4 #include <cstdio>
 5 #define LL __int64
 6 using namespace std;
 7 const int maxn=100001;
 8 struct node
 9 {
10     LL w;
11     LL s;
12 }p[maxn];
13 bool cmp(const node a, const node b)
14 {
15     return a.w+a.s<b.w+b.s;
16 }
17 int main()
18 {
19     int i,n;
20     LL max,a,b;
21     while(~scanf("%d",&n))
22     {
23         for(i=0;i<n;i++)
24             scanf("%I64d%I64d",&p[i].w,&p[i].s);
25         sort(p,p+n,cmp);
26         a=p[0].w;
27         max=-p[0].s;
28         for(i=1;i<n;i++)
29         {
30             b=a-p[i].s;
31             a+=p[i].w;
32             if(b>max) 
33                 max=b;
34         }
35         if(max<0) 
36             puts("0");
37         else 
38             printf("%I64d\n",max);
39     }
40     return 0;
41 }