1. 假设#

我们先假设国王后面只有两个大臣，而且假设国王拿着的是 $a_0,b_0$，第一个大臣拿的是 $a_1,b_1$，第二个大臣拿的是 $a_2,b_2$，我们有两种顺序。

• 第一个大臣在前面，那么第一个大臣得到的奖金就是 $\frac{a_0}{b_1}$，第二个大臣拿到的奖金就是 $\frac{a_0\times a_1}{b_2}$，最高的奖赏就是 $\max{(\frac{a_0}{b_1},\frac{a_0\times a_1}{b_2})}$。

• 第二个大臣在前面，那么第二个大臣得到的奖金就是 $\frac{a_0}{b_2}$，第一个大臣拿到的奖金就是 $\frac{a_0\times a_2}{b_1}$，最高的奖赏就是 $\max{(\frac{a_0}{b_2},\frac{a_0\times a_2}{b_1})}$。

2. 推导#

现在我们就要来比较最高的奖赏，即比较 $\max{(\frac{a_0}{b_2},\frac{a_0\times a_2}{b_1})}$ 和 $\max{(\frac{a_0}{b_1},\frac{a_0\times a_1}{b_2})}$ 谁更小。

我们发现 $\frac{a_0}{b_1}$ 一定小于等于 $\frac{a_0\times a_2}{b_1}$（因为 $a_2$ 是大于 0 的整数，即 $a_2 \ge 1$，不会变小），同理 $\frac{a_0}{b_2}$ 一定小于等于 $\frac{a_0\times a_1}{b_2}$。所以我们可以将式 $[a]$ 转化为求 $\min{(\frac{a_0\times a_1}{b_2},\frac{a_0\times a_2}{b_1})[a]}$ 的答案。

我们把 $\frac{a_0\times a_1}{b_2}$ 和 $\frac{a_0\times a_2}{b_1}$ 同时除 $a_0$，在乘上 $b_1\times b_2$，就把这两个式子化简为 $b_1\times a_1$ 和 $b_2\times a_2$。发现什么没有？我们把结果的大小比较转化为了大臣手上数的乘积比较，如果 $a_1\times b_1$ 小于 $a_2\times b_2$，那么就把 1 号大臣排在前面，否则排在后面。

1. 假设#

我们假设有两个产品 $x$ 和 $y$，$x$ 产品在 A 车间加工时间是 $a_x$，同理，其他的分别为 $b_x$、$a_y$、$b_y$。

• $x$ 产品先做，那么 $x$ 产品所有的时间就是 $a_x+b_x$，由于 $y$ 产品要等到 $x$ 产品加工完才行，那么 $y$ 产品在 A 车间加工就需要 $a_x+a_y$ 的时间（$a_x$ 的等待时间），而此时 $x$ 产品在 B 车间加工了 $a_y$ 的时间，还需要 $\max{(b_x-a_y,0)}$ 的时间加工，所以 $y$ 产品在 B 车间需要 $\max{(b_x-a_y,0)}+b_y$ 的时间加工。由于 $y$ 产品肯定是等到 $x$ 产品加工后才结束，所以花费的总时间是 $a_x+a_y+\max{(b_x-a_y,0)}+b_y$ 的时间。

• 同理 $y$ 产品先做就需要花费 $a_x+a_y+\max{(b_y-a_x,0)}+b_x$ 的时间。

2. 推导#

现在我们需要比较 $x$ 产品先做和 $y$ 产品先做的时间，即求出 $\min(a_x+a_y+\max(b_x-a_y,0)+b_y,a_x+a_y+\max(b_y-a_x,0)+b_x)[b]$

不难发现 $x\pm \max(a,b)=\max(x\pm a,x\pm b)$，对于 $\min$ 也成立，所以 $[b]$ 式就可以化简为：

$\min(a_x+a_y+\max(b_x,a_y)-a_y+b_y,a_x+a_y+\max(b_y,a_x)-a_x+b_x)$

$=\min(a_x+b_y+\max(b_x,a_y),a_y+b_x+\max(b_y,a_x))$

$=\min(\max(b_x,a_y)-a_y-b_x,\max(b_y,a_x)-a_x-b_y)+a_x+a_y+b_x+b_y$

$=\min(\max(-a_y,-b_x),\max(-a_x,-b_y))+a_x+a_y+b_x+b_y$

至于继续的推导，需要用到 Johnson 定理，感兴趣的读者可以自己去了解一下。

最终的排序方法是将 $\min(a_x,a_y) < \min(b_x,b_y)$ 的 $x$ 排前面。

1. 假设#

假设有两头牛 $a$ 和 $b$，那么它们的体重分别是 $w_a$ 和 $w_b$，力量是 $s_a$ 和 $s_b$。

如果现在只有这两头牛，那么：

• $a$ 在上面，那么 $a$ 的压扁指数为 $-s_a$，$b$ 的压扁指数为 $w_a-s_b$，总压扁指数为 $\max(-s_a,w_a-s_b)$。（注意这里不能直接省去 $-s_a$，虽然它为负数，但当 $w_a-s_b<-s_a$ 时就会取 $-s_a$。）

• $b$ 在上面，那么同理，总压扁指数为 $\max(-s_b,w_b-s_a$)。

2. 进一步的假设#

如果我们要使 $a$ 在上面，那么我们该怎么做呢？

我们需要满足 $\max(-s_a,w_a-s_b) < \max(-s_b,w_b-s_a)$。

易证 $-s_a < w_b-s_a,-s_b < w_a-s_b$ 所以 $\max(-s_a,w_a-s_b)$ 就可以变为 $w_a-s_b$，同理 $\max(-s_b,w_b-s_a)$ 变为 $w_b-s_a$。

因为我们要使 $w_a-s_b < w_b-s_a$，简单移项便可以得到 $w_a+s_a<w_b+s_b$。

所以如果要使 $a$ 在上面，必须要 $w_a+s_a<w_b+s_b$。