【和排序】 耍杂技的牛

传送门

题意

\(n\)头牛，每头牛有重量\(w_{i}\)和强壮程度\(s_{i}\)，牛与牛之间垂直堆叠，每头牛的风险值是他上面不包括他自己所有牛的重量之和减他的强壮程度，求所有奶牛风险值中的最大值尽可能的小

数据范围

\(\begin{array}{l}1 \leq N \leq 50000 \\ 1 \leq w_{i} \leq 10,000 \\ 1 \leq s_{i} \leq 1,000,000,000\end{array}\)

题解

贪心策略：按照\(w\)和\(s\)的和进行排序
贪心证明: 邻项交换
假设排序后当前从下往上第\(i\)头牛和第\(i+1\)头牛的风险值分别为\(\sum_{j=0}^{i-1} w_{j}-s_{i} ，\quad \sum_{j=0}^{i} w_{j}-s_{i+1}\)
交换这两头牛后的风险值分别为\(\sum_{j=0}^{i-1} w_{j}-s_{i+1}，\sum_{j=0}^{i-1} w_{j}+w_{i+1}-s_{i}\)
去掉重复项\(\quad \sum_{j=0}^{i-1} w_{i-1}\)后交换前和交换后的值分别为

• 交换前：\(-s_{i}\) ，\(w_{i}-s_{i+1}\)
• 交换后：\(-s_{i+1}\)，\(w_{i+1}-s_{i}\)

易知

• \(w_{i}-s_{i+1} > -s_{i+1}\)
• \(w_{i+1}-s_{i} > -s_{i}\)

所以只需要比较\(w_{i}-s_{i+1}\)和\(w_{i+1}-s_{i}\)的大小即可
\(w_{i}-s_{i+1} < w_{i+1}-s_{i}\)
即\(w_{i} + s_{i} < w_{i+1} + s_{i+1}\)
所以和越小的风险值越小

Code

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for(int i=a;i<n;i++)
#define fi first 
#define se second 
#define ll long long
typedef pair<long long,long long> pll;
const int N=5e4+10;
int n;
pll cow[N];

int main(){
    scanf("%d",&n);
    rep(i,0,n){
        ll x,y;
        scanf("%lld%lld",&x,&y);
        cow[i].fi=x+y;
        cow[i].se=y;
    }    
    sort(cow,cow+n);
    ll now=0;
    ll mx=-1e18;
    rep(i,0,n){
        mx=max(mx,now-cow[i].se);
        now+=cow[i].fi-cow[i].se;
    }
    printf("%lld\n",mx);
}