Description：

$n$ 头牛叠在一起，每头牛有重量和力量，安排一个顺序使得每头牛上方的牛的总重量 $-$ 这头牛的力量的最大值最小。

$1\le n \le 50000$

Solution：

类似国王游戏，设相邻的两头牛 $a$ 和 $b$ ， $a$ 上方牛的总重为 $W$ ， $a$ 在上的不稳定度为 $\max(W-s_a,W+w_a-s_b)$ ， $b$ 在上的不稳定度为 $\max(W-s_b,W+w_b-s_a)$ ，由于 $W+w_b-s_a>W-s_a$ ， $W+w_a-s_b>W-s_b$ ，所以实际相当于 $W+w_a-s_b$ 和 $W+w_b-s_a$ 比较大小，要想让 $a$ 在前面，就要让 $W+w_a-s_b<W+w_b-s_a$ ，即 $w_a+s_a<w_b+s_b$ ，按 $w+s$ 排序即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

#define MAXN 50010

struct cow

{

	int w,s;

	int val;

}s[MAXN];

bool cmp_val(cow a,cow b){return a.val < b.val;}

int main()

{

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)

	{

		scanf("%d%d",&s[i].w,&s[i].s);

		s[i].val = s[i].w + s[i].s;

	}

	sort(s + 1,s + 1 + n,cmp_val);

	int sum_w = 0;

	int ans = -0x3f3f3f3f;

	for(int i = 1;i <= n;++i)

	{

		ans = max(ans,sum_w - s[i].s);

		sum_w += s[i].w;

	}

	cout << ans << endl;

	return 0;

}