125. 耍杂技的牛

125. 耍杂技的牛

贪心

该题贪心策略类似于国王的游戏，先猜一套方案：将w+s升序排序。
证明：就是证明降序时交换前的最大值会大于等于交换后的最大值（所以降序需要变成升序），升序则小于等于。

#include
#include
using namespace std;
const int N = 50010;
struct Node{
    int w,s;
    bool operator<(const Node &t) const{
        if(w != t.w) return w < t.w;
        return s < t.s;
    }
}node[N];
int main(){
    int n; cin>>n;
    for(int i = 0; i < n; i++){
        cin>>node[i].w>>node[i].s;
        node[i].w += node[i].s; //w+s
    } 
    sort(node,node+n);
    int ans = -0x3f3f3f3f, sum = 0;
    for(int i = 0; i < n; i++){
        sum -= node[i].s;
        ans = max(ans,sum);
        sum += node[i].w;
    }
    cout<