POJ 3045 Cow Acrobats 贪心\二分

题目链接： 点我
题目分析： 本来做的是二分的练习题，但在想的过程中发现贪心就好了。每次只考虑最下面选哪个牛，策略是选择w+v最大的那个，设其他任一牛为w’，v’，所有牛总重为sum，那么两头牛分别在最下层的风险是sum-w-v和sum-w’-v’，所以每次都选择w+v最大的牛放在最下面。将w+v排序后贪心即可。
附：二分和贪心的代码

贪心：

Problem: 3045       User: ChenyangDu
Memory: 544K        Time: 94MS
Language: C++       Result: Accepted#include
#include
#include
#includeusing namespace std;const int maxn = 50000+5,INF = 1000000000+7;
int n,sum;struct cow{int w,v;}in[maxn];bool cmp(cow a,cow b){return a.w+a.vint main(){//freopen("in.txt","r",stdin);scanf("%d",&n);for(int i=0;iscanf("%d%d",&in[i].w,&in[i].v);}sort(in,in+n,cmp);int ans = -INF;for(int i=0;iprintf("%d",ans);return 0;
}

二分：

Problem: 3045       User: ChenyangDu
Memory: 612K        Time: 125MS
Language: C++       Result: Accepted
Source Code
#include
#include
#include
#includeusing namespace std;const int maxn = 50000+5,INF = 1000000000+7;
int n,sum,sum_back;struct cow{int w,v;}in[maxn];bool cmp(cow a,cow b){return a.w+a.v>b.w+b.v;
}bool ok(int x){sum = sum_back;for(int i=0;iif(sum > a.w + a.v + x){return false;}sum -= a.w;}return true;
}int main(){//freopen("in.txt","r",stdin);scanf("%d",&n);for(int i=0;iscanf("%d%d",&in[i].w,&in[i].v);sum += in[i].w;}sum_back = sum;sort(in,in+n,cmp);int l = -INF,r = INF;while(r-l>1){int mid = (l+r)>>1;if(ok(mid))r = mid;else l = mid;}cout<return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！