这题略屌……
考虑如下：
对于相邻的两头牛,它们交换位置不影响其他的任何牛,只改变这两头牛的风险值.
记sum为这两头牛上面的牛的体重总和.i在j上面
Riski=sum-si
Riskj=sum+wi-sj
交换位置
Riski'=sum+wj-si
Riskj'=sum-sj
方案1优于方案2,则max{Riski,Riskj}<max{Riski',Riskj'}
而Riskj>Riskj'
所以Riski'>max{Riski,Riskj},且Riski'>Riskj'.
解之得
wj-si>sj
wj-si>wi-sj
wj-si>si
我们只需要中间的一条.记ti=si+wi
则方案1优于方案2等价于ti<tj,即ti小的在上会更优.
所有就将所有的小牛牛们按照W+s之和排序，由小到大。
然后从上往下的计算，找出最大值，记录下来。
AC Memory : 976KB Time : 94MS
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int x,y;
}n[60000];
bool cmp(node a,node b)
{
return (a.x+a.y)<(b.x+b.y);
}
int sum[60000];
int main()
{
int N;
while(scanf("%d",&N)!=EOF)
{
for(int i=1;i<=N;i++)
scanf("%d%d",&n[i].x,&n[i].y);
sort(n+1,n+N+1,cmp);
sum[0]=0;
int ans=-999999999;
for(int i=1;i<=N;i++)
{
sum[i]=sum[i-1]+n[i].x;
ans=max(ans,sum[i-1]-n[i].y);
}
printf("%d\n",ans);
}
return 0;
}