卡在此题，贪心不过关。
对于任意的牛，她的压扁指数等于摞在她上面的所有奶牛的总重（当然不包括她自己）减去它的力量。可见题中两个数据：重量w和力量s是1：1加减法转化的，于是有按照该牛重量+力量来排序的贪心策略。证明：若有相邻两牛x和y，有wx+sx<wy+sy，则有wx-sy<wy-sx，即x牛放y牛上答案更优，可知对于最终的答案序列，w+s一定为不下降排列；再考虑是否最优：若最终答案序列与贪心得出的不一样，由于各w+s各不相同时从小到大的排序只有一个（相同时也无妨，因为不会影响答案，即wx+sx=wy+sy => wx-sy=wy-sx），则只能是最终答案序列存在逆序对，就不是最终答案了，矛盾，故知贪心策略正确。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 5 using namespace std; 6 7 const int N=50005; 8 9 int w[N],s[N],xu[N],n; 10 11 inline int read() 12 { 13 int x=0; 14 char ch=getchar(); 15 while(!isdigit(ch)) ch=getchar(); 16 while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar(); 17 return x; 18 } 19 20 inline bool cmp(const int &a,const int &b) 21 { 22 return w[a]+s[a]<w[b]+s[b]; 23 } 24 25 int main() 26 { 27 n=read(); 28 for(int i=1;i<=n;++i) 29 { 30 w[i]=read();s[i]=read();xu[i]=i; 31 } 32 sort(xu+1,xu+1+n,cmp); 33 int wei=0,ans=-2100000000,d; 34 for(int i=1;i<=n;++i) 35 { 36 d=wei-s[xu[i]]; 37 ans=max(ans,d); 38 wei+=w[xu[i]]; 39 } 40 cout<<ans; 41 return 0; 42 }
可联想到，若两数据转化比例不为1:1，但转化方式仍为加减转化，可用类似操作，不过排序时变量有系数不同罢了。