题目链接： 点我 题目分析： 本来做的是二分的练习题，但在想的过程中发现贪心就好了。每次只考虑最下面选哪个牛，策略是选择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<iostream> #include<cstdio> #include<cstring> #include<algorithm> using 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.v<b.w+b.v; } int main(){ //freopen("in.txt","r",stdin); scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d%d",&in[i].w,&in[i].v); } sort(in,in+n,cmp); int ans = -INF; for(int i=0;i<n;i++){ ans = max(ans,sum - in[i].v); sum += in[i].w; } printf("%d",ans); return 0; }二分：
Problem: 3045 User: ChenyangDu Memory: 612K Time: 125MS Language: C++ Result: Accepted Source Code #include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using 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;i<n;i++){ cow a = in[i]; if(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;i<n;i++){ scanf("%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<<r; return 0; }