贪心法

容易发现对于任意两个相邻的奶牛, 如果进行交换, 在这两个奶牛之前的奶牛风险不受影响, 在这两个奶牛之后的奶牛风险也不受影响.
因此, 非常自然的想法是观察一下这两个奶牛交换前与交换后的风险变化, 推一下公式, 容易发现一个指标:
Wi + Si
这个指标越小, 就应该放在前面, 越大, 就应该放在后面, 从而使最大风险减少.
对于任意两个相邻的奶牛都是如此, 因此, 如果基于这个指标进行升序排序, 可以让最大风险最小化.

时间复杂度

O(N * log(N))

Python 代码

N = int(input())
cows = []
for i in range(N):
    W, S = map(int, input().split())
    cows.append((W + S, W, S))
cows.sort()
ans = float("-inf")
s = 0
for _, W, S in cows:
    ans = max(ans, s - S)
    s += W
print(ans)