题意:一堆牛宝宝叠罗汉。。。每只牛宝宝都有它的重量和力量值,求出各种叠放秩序中最大危险值中的最小值【语文不好。。请原谅
贪心::>_<::,就是最优放置的方式w2-s1>w1-s2,就是w2+s2>w1+s1.。。。。排序就是了。。。。
代码(话说因为多打了一个括号然后我华丽丽地wa了两个小时。。真是不忍直视)
#include <cstdio> #include <algorithm> using namespace std; struct cow { int w,s; }c[50005]; int n,mi; bool cmp(const cow &a,const cow &b) { return a.s+a.w<b.s+b.w; } int main() { int n,sum=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d%d",&c[i].w,&c[i].s); } sort(c+1,c+1+n,cmp); //for(int i=1;i<=n;i++) //printf("%d %d\n",c[i].w,c[i].s); mi=-1000000000; for(int j=1;j<=n;j++) { if(mi<sum-c[j].s) // printf("%d",sum-c[j].s); mi=sum-c[j].s; // printf("%d ",mi); sum+=c[j].w; } //printf("\n"); printf("%d\n",mi); }
后补:
这个题后来又出现在了二分的题目里。。。。。然后实在是没想出来什么好的二分。。小马哥说是比较牵强的二分了。。
就是还是按照原来的规则排序,然后对结果进行二分,如果排序后危险值有大于该值的则增大危险值,否则缩小。
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=50010; int sum[maxn],n; struct node { int w,s; }cow[maxn]; bool cmp(const node &a,const node &b) { return a.s+a.w<b.s+b.w; } bool ok(int m) { for(int i=n;i>=1;i--) { if(m<sum[i-1]-cow[i].s) return false; } return true; } int main() { int l=0,r=0; scanf("%d",&n); for (int i=1;i<=n;i++) { scanf("%d%d",&cow[i].w,&cow[i].s); l=max(l,cow[i].s); r+=cow[i].w; } sort(cow+1,cow+n+1,cmp); for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+cow[i].w; } l=-l; while(l+1<r) { int mid=(l+r)/2; if(ok(mid)) r=mid; else l=mid; } if(ok(l)) printf("%d",l); else printf("%d",r); }