贪心题集

hdu4296

堆积木，每层积木有一个重量w，强度s。每层积木有一个伤害，它上面的积木和-它的强度si，求不同摆放方式的最大的伤害值的最小值。伤害一定大于0；

两个相邻积木i，j如何摆放使最大的伤害值最小。

第一种i在上：sum - s_i；sum + w_i - s_j

第二种j在上：sum - s_j；sum + w_j - s_i

第一种比较优：sum + w_i - s_j<sum + w_j - s_i即wi+si >wj+sj;即wi+si比较小的摆在上面比较好。

 1 #include<bits/stdc++.h>
 2 #define MAXN 100010
 3 using namespace std;
 4 
 5 struct Floor
 6 {
 7     int w,s;
 8 };
 9 Floor floors[MAXN];
10 bool cmp(Floor a,Floor b)
11 {
12     return a.w+a.s < b.w+b.s;
13 }
14 int main()
15 {
16     int n;
17     while(~scanf("%d",&n))
18     {
19         for(int i = 0; i < n; i++)
20             scanf("%d%d",&floors[i].w,&floors[i].s);
21         sort(floors,floors+n,cmp);
22         long long Sum = 0, Max = 0;
23         for(int i = 0; i < n;i++)
24         {
25             Max = max(Max,Sum - floors[i].s);
26             Sum += floors[i].w;
27         }
28         printf("%I64d
",Max);
29     }
30     return 0;
31 }