题意
对于牛i,其危险度$d1[i] = w[1]+…+w[i-1] - s[i]$,
对于牛i+1,其危险度$d1[i+1] = w[1]+…+w[i] - s[i+1]$a。
若调换牛i和牛i+1的位置,则$d2[i] = w[1]+…+w[i-1]+w[i+1] - s[i],d2[i+1] = w[1]+…+w[i-1] - s[i+1]$
因为都有公共部分$w[1]+…+w[i+1]$,这部分消去,只看$d1[i] = -s[i], d1[i+1] = w[i]-s[i+1], d2[i] = w[i+1]-s[i], d2[i+1] = -s[i+1]$
显然有$d1[i+1] = w[i] - s[i+1] > d2[i+1] = -s[i+1]$,如果$d1[i+1] > d2[i]$的话,$d1[i+1] > max(d2[i+1],d2[i])$,此时可见换位之后,这两头牛的压力值的最大值减小了,即若$w[i] - s[i+1] > w[i+1]-s[i]$,即若$w[i] + s[i] > w[i+1] + s[i+1]$ 的话,第i头牛在第i+1头牛下方是更优的
由此可得,对于任意的两头牛,都应有s+w小者在下方,于是对于整个牛群来说,应让s+w小的拍在下面,如果s+w相等,那么显然应该让w大的排在下面
代码
#include <iostream>
#include <algorithm>
#define x first
#define y second
using namespace std;
const int N = 50010;
typedef pair<int,int> PII;
PII cow[N];
int n;
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
int s,w;
cin >> w >> s;
cow[i] = {w+s,w};
}
sort(cow,cow+n);
int res = -1e8;
for (int i = 0, sum = 0; i < n; i++)
{
int danger = sum-(cow[i].x-cow[i].y);
res = max(res,danger);
sum += cow[i].y;
}
cout << res << endl;
return 0;
}