奶牛叠罗汉问题

题目描述

农民约翰的 $N$ 头奶牛（编号为 $1..N$）计划逃跑并加入马戏团，为此它们决定练习表演杂技。

奶牛们不是非常有创意，只提出了一个杂技表演：

叠罗汉，表演时，奶牛们站在彼此的身上，形成一个高高的垂直堆叠。

奶牛们正在试图找到自己在这个堆叠中应该所处的位置顺序。

这 $N$ 头奶牛中的每一头都有着自己的重量 $W_i$ 以及自己的强壮程度 $S_i$。

一头牛支撑不住的可能性取决于它头上所有牛的总重量（不包括它自己）减去它的身体强壮程度的值，现在称该数值为风险值，风险值越大，这只牛撑不住的可能性越高。

您的任务是确定奶牛的排序，使得所有奶牛的风险值中的最大值尽可能的小。

输入格式

第一行输入整数 $N$，表示奶牛数量。

接下来 $N$ 行，每行输入两个整数，表示牛的重量和强壮程度，第 $i$ 行表示第 $i$ 头牛的重量 $W_i$ 以及它的强壮程度 $S_i$。

输出格式

输出一个整数，表示最大风险值的最小可能值。

输入输出样例 #1

输入 #1

3
10 3
2 5
3 3

输出 #1

2

输入输出样例 #2

输入 #2

4
1 10
2 9
3 8
4 7

输出 #2

3

限制条件

• $1 \le N \le 50000$
• $1 \le W_i \le 10000$
• $1 \le S_i \le 1,000,000,000$

问题分析

设奶牛的顺序为某个排列，对于位置 $i$ 的奶牛（从下往上数）：

风险值 $R_i = (\sum_{j=1}^{i-1} W_j) - S_i$

即：它上面所有牛的重量之和减去它自身的强壮程度。

目标：最小化 $\max_{i=1}^N R_i$

贪心策略

这是一个典型的排序问题，类似于"国王游戏"或"耍杂技的牛"问题。

对于两头相邻的牛 $i$ 和 $i+1$，考虑交换它们的位置是否会使最大风险值变小。

设当前 $i$ 在 $i+1$ 上面，总重量在上面的部分为 $T$（$i$ 和 $i+1$ 上面的牛的总重量）。

• 当前顺序：$i$ 在 $i+1$ 上面

  • 牛 $i$ 的风险值：$T - S_i$
  • 牛 $i+1$ 的风险值：$T + W_i - S_{i+1}$
  • 最大风险值：$\max(T - S_i, T + W_i - S_{i+1})$

• 交换后顺序：$i+1$ 在 $i$ 上面

  • 牛 $i+1$ 的风险值：$T - S_{i+1}$
  • 牛 $i$ 的风险值：$T + W_{i+1} - S_i$
  • 最大风险值：$\max(T - S_{i+1}, T + W_{i+1} - S_i)$

我们希望在两种顺序中选择使最大风险值较小的那种。

比较两种顺序的最大风险值，即比较： $\max(T - S_i, T + W_i - S_{i+1})$ 和 $\max(T - S_{i+1}, T + W_{i+1} - S_i)$

由于 $T$ 相同，可以去掉 $T$，比较： $\max(-S_i, W_i - S_{i+1})$ 和 $\max(-S_{i+1}, W_{i+1} - S_i)$

由于 $S_i, S_{i+1} > 0$，所以 $-S_i$ 和 $-S_{i+1}$ 都是负数，而 $W_i - S_{i+1}$ 和 $W_{i+1} - S_i$ 可能为正也可能为负。

实际上，我们最终会发现最优排序是按照 $W_i + S_i$ 从小到大排序。

结论

按照 $W_i + S_i$ 从小到大的顺序排列奶牛，可以得到最小的最大风险值。

样例解释 #1

奶牛数据：

1. $W=10, S=3, W+S=13$
2. $W=2, S=5, W+S=7$
3. $W=3, S=3, W+S=6$

按 $W+S$ 排序：奶牛3 → 奶牛2 → 奶牛1

从下往上排列：

• 最下面：奶牛3（$W=3, S=3$），风险值 = $0 - 3 = -3$
• 中间：奶牛2（$W=2, S=5$），风险值 = $3 - 5 = -2$
• 最上面：奶牛1（$W=10, S=3$），风险值 = $(3+2) - 3 = 2$

最大风险值 = $\max(-3, -2, 2) = 2$

输出 $2$。