125. 耍杂技的牛

 结论：

 证明： 第一个不用证明，很明显

第二个：

假设wi+si>w(i+1)+s(i+1) 

 由于wi+si > w(i+1)+s(i+1)        wi+si > si  所以交换后  两头牛的风险的最大值一定是小于交换前两头牛的风险的最大值的！ 那么总体的风险的最大值就不可能增加，只可能不变或减小。所以得证。

所以我们就按wi+si从小到大的顺序依次从上到小安排牛，这样的风险的最大值就会是所有情况里的最小值

#include 
#include 
using namespace std;
const int N = 50010;
typedef pair<int, int> PII;
PII q[N];
int n;

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        int w, s;
        cin >> w >> s;
        q[i] = {w + s, s};
    }
    
    sort(q, q + n);
    
    int ans = -2e9, sum = 0;  // sum = 0 表示最上面的那头牛的上面的牛的重量为0 （即没有牛） 然后依次往下面增加上面牛的重量
    for(int i = 0; i < n; i++)
    {
        int s = q[i].second, w = q[i].first - s;
        ans = max(ans, sum - s);
        sum += w;
    }
    
    cout << ans << endl;
    
    return 0;
}