$$\color{Red}{ 耍杂技的牛——推公式}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

1. 贪心证明

此题代码很简单，重点是推理排序不等式的过程。

我们先假设我们有n头牛，已经完成了排序，或者是还差一步完成排序。

看完这道题可以立马去看 我的能量石详细题解 ，贪心融合背包问题，进行强化

这里先设定排列后为0 -> n - 1的下标，数字越小代表在越下面

假设我们任取中间的第i头和第i + 1头牛，他们此时的风险值为：

第i头: Σ(k ∈ i+1 -> n) w(k) - si
i+1头: Σ(k ∈ i+2 -> n) w(k) - si+1

把相同的求和部分去除
第i头: wi+1 -si
i+1头: -si+1

假设此时交换这两头牛，显然对他们俩之上的牛没有任何影响（因为这些牛头顶的牛没有变化），对他们之下的牛也没有任何影响（因为虽然他们俩交换，但头顶牛的总重量没有变化）
仅他们两个的风险值发生了变化 那么他们的风险值变为：

第i头: -si
i+1头: wi -si+1

我们找交换后到底是否合适，就是在这四个值找最大值，最大值在交换前，说明交换后更合适，最大值在交换后，说明交换前更合适。

显然任意的w和s都应该大于0，所以加上负号显然必定小于零，我们找最大值就忽略小于0的。

我们只需要看 交换前的wi+1 - si 和 交换后的wi - si+1谁更大即可。

当前者大于后者，说明最大值出现在交换前，交换后更合适，此时 wi+1 - si > wi - si+1，移项: wi+1 + si+1 > si + wi

即应该把一个自身重量和强壮度的和更大的牛放在更下面，会让风险值的最大值变得更小。

1. java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, N = 50010;

    static class Node {
        int w, s;

        public Node(int w, int s) {
            this.w = w;
            this.s = s;
        }
    }

    static Node[] nodes = new Node[N];

    public static void main(String[] args) throws IOException {
        n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            String[] str = br.readLine().split(" ");
            int w = Integer.parseInt(str[0]);
            int s = Integer.parseInt(str[1]);
            nodes[i] = new Node(w, s);
        }
        //下标为0代表在最下面
        Arrays.sort(nodes, 0, n, (o1, o2) -> (o2.w + o2.s) - (o1.w + o1.s));
        int res = -(int)0x3f3f3f3f;
        int weight = 0;
        for (int i = n-1; i >= 0; i--) {
            res = Math.max(res, weight - nodes[i].s);
            weight += nodes[i].w;
        }
        System.out.println(res);        
    }
}

2. python3代码

n = int(input())
data = [list(map(int, input().split())) for i in range(n)]

data.sort(key = lambda x: x[0] + x[1])

ans = -float('inf')
weight = 0

for w, s in data:
    ans = max(ans, weight - s)
    weight += w

print(ans)