首页 > 代码库 > 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 (贪心)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。