首页 > 代码库 > HDU - 4296 Building (贪心)

HDU - 4296 Building (贪心)

题意:有n个板,每个板有重量和强度两个属性,把板叠在一起,对于每个板有个PDV值,计算方式为这个板上面的板的重量和减去这个板的强度,

然后求这些PDV中最大值(不同的排列方式会有不同的最大值)的最小值。

 

首先就是怎么叠放的问题,一般思路就是把轻的放上面,硬度大的放下面,一开始我就是这样写的,然后就一直wrong。(QAQ...)

换种思路,直接从题意中推导:

对于相邻放置的两块板,设两块板为i,j他们上面的重量为sum
1) a=sum-si;b=sum+wi-sj;

 交换两个板的位置

2)a‘=sum+wj-si;b‘=sum-sj;

如果1优于2,求解得有效的条件为wj-si>wi-sj

即wj+sj>wi+si

然后后面就简单了。注意一下数据sum可能会很大要用long long 就可以了。

哦,还有一件事,用cin输入会时间超限,选择用scanf输入就ok了。

 

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstdio>
 4 using namespace std;
 5 
 6 struct Build{
 7     int w;
 8     int s;
 9 }build[100010];
10 
11 
12 
13 int main(){
14     int n;
15     while(scanf("%d",&n)!=EOF){
16         for(int i=1;i<=n;i++)
17         scanf("%d %d",&build[i].w,&build[i].s);
18         sort(build+1,build+n+1,cmp);
19         long long maxx=0,sum=0;
20         for(int i=1;i<=n;i++){
21             maxx=max(maxx,sum-build[i].s);
22             sum=sum+build[i].w;
23         }
24         printf("%lld\n",maxx);
25     }
26     return 0;
27 }

 

 

HDU - 4296 Building (贪心)