要点

1. 贪心策略的推导方法类似于AcWing 734. 能量石（主要刷题少，只想到了这题，本人题解（Java 贪心+排序+01背包）），不过这题更绕
2. 假设存在某一种最优解，则对于其中任意两个相邻的牛$Cow_i$、$Cow_{i+1}$，记$Cow_0 \sim Cow_{i-1}$的重量总和为$Sum$，这两头牛的最大风险值为$D_1 = max(Sum-S_i, Sum+W_i-S_{i+1})$
   • 此时交换两者次序，则最大风险值变为$D_2 = max(Sum-S_{i+1}, Sum+W_{i+1}-S_i)$，而前者作为一种最优解（可能不唯一），交换次序后，新的最大风险值必不可能更优，即$D_1 \leq D_2 \Longrightarrow max(Sum-S_i, Sum+W_i-S_{i+1}) \leq max(Sum-S_{i+1}, Sum+W_{i+1}-S_i)$
   • 观察到前项的$Sum-S_i$必定小于后项的$Sum+W_{i+1}-S_i$，所以前项的$Sum-S_i$必定小于后项两个式子的最大值，满足不等式要求，原式转化为$Sum+W_i-S_{i+1} \leq max(Sum-S_{i+1}, Sum+W_{i+1}-S_i)$
   • 又观察到前项仅存的$Sum+W_i-S_{i+1}$必定大于后项的$Sum-S_{i+1}$，所以为了满足不等式，必有$Sum+W_i-S_{i+1} \leq Sum+W_{i+1}-S_i \Longrightarrow W_i-S_{i+1} \leq W_{i+1}-S_i$
   • 因此贪心策略：最优解中任意相邻两项必定满足$W_i-S_{i+1} \leq W_{i+1}-S_i$
3. 推导如上，代码如何实现？先读入所有牛的重量和强壮程度，按照$W_i-S_{i+1} \leq W_{i+1}-S_i$的关系进行排序，最终所得的有序序列即为最优策略，遍历求最大风险即可
4. 此外，$W_i-S_{i+1} \leq W_{i+1}-S_i \Longrightarrow W_i+S_i \leq W_{i+1}+S_{i+1}$，在存入牛的强壮程度时，可转为存重量与强壮程度之和，最后按该数值升序排列即可

代码

普通

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n;

    static class Cow {
        public int w, s;

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

    public static void main(String[] args) {
        n = scanner.nextInt();
        Cow[] cows = new Cow[n];
        for (int i = 0; i < n; i++)
            cows[i] = new Cow(scanner.nextInt(), scanner.nextInt());
        Arrays.sort(cows, (o1, o2) -> o1.w - o2.s - o2.w + o1.s);
        int ans = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, sum - cows[i].s);
            sum += cows[i].w;
        }
        System.out.println(ans);
    }
}

存重量与强壮程度之和

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n;

    static class Cow {
        public int w, s;

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

    public static void main(String[] args) {
        n = scanner.nextInt();
        Cow[] cows = new Cow[n];
        int w, s;
        for (int i = 0; i < n; i++) {
            w = scanner.nextInt();
            s = scanner.nextInt();
            cows[i] = new Cow(w, w + s);
        }
        Arrays.sort(cows, Comparator.comparingInt(o -> o.s));
        int ans = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < n; i++) {
            ans = Math.max(ans, sum - (cows[i].s - cows[i].w));
            sum += cows[i].w;
        }
        System.out.println(ans);
    }
}