耍杂技的牛

思考排序策略：

Part.1

按 $W_i+S_i$ 排序。

设要将第 $i$ 和第 $i+1$ 头奶牛确定位置，且 $W_i+S_i<W_{i+1}+S_{i+1}$。

未交换前

第 $i$ 头的风险值：$\sum\limits_{j=1}^{i-1}W_j-S_i$。

第 $i+1$ 头的风险值：$\sum\limits_{j=1}^{i-1}W_j+W_i-S_{i+1}$。

上减下，得 $S_{i+1}-W_i-S_i$。

该式正负不确定。

交换后

第 $i$ 头的风险值：$\sum\limits_{j=1}^{i-1}W_j+W_{i+1}-S_i$。

第 $i+1$ 头的风险值：$\sum\limits_{j=1}^{i-1}W_j-S_{i+1}$。

上减下，得 $W_{i+1}+S_{i+1}-S_i$。

因为 $W_i>0$，所以 $W_{i+1}+S_{i+1}-S_i>0$。

比较

将两式各减去 $(S_{i+1}-S_i)$，得：

$$\begin{aligned} & S_{i+1}-W_i-S_i-(S_{i+1}-S_i) \\ = & \ S_{i+1}-W_i-S_i-S_{i+1}+S_i \\ = & \ -W_i \\ \\ & W_{i+1}+S_{i+1}-S_i-(S_{i+1}-S_i) \\ = & \ W_{i+1}+S_{i+1}-S_i-S_{i+1}+S_i \\ = & \ W_{i+1} \end{aligned}$$

因为 $W_i>0,W_{i+1}>0$，所以前式小于后式，即该贪心策略正确。