本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-24 16:48:41

考虑证明按照 $s + w$ 贪心的正确性。

我们的贡献和位置是无关的，因此我们要证的仅仅是当 $s_i + w_i \lt s_j + w_j$ 时，若 $j$ 可以放在 $i$ 上头，那么 $i$ 就一定能放在 $j$ 上头。也就是说：任意一种方案，都可以是排序后顺序构造。

设 $p_i$ 表示当前方案中 $1$ 到 $i$ 所有箱子的重量和，那么我们已知 $p_{i-1} \le s_i, p_{j-1}\le s_j$，要证 $p_{i-1}\le s_j, p_{j-1} - w_i + w_j \le s_i$。

放缩代入得证。