自动搬运

查看原文

来自洛谷，原作者为

	CloudDreamLake Let's go into cdlake!

搬运于2025-08-24 22:18:56，当前版本为作者最后更新于2024-11-03 22:10:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

先找出总时间的表达式：

$$\max_{i=1}^{n} \left( \sum_{j=1}^ia_j + \sum_{j=i}^n b_j \right) $$

解释：

如果对其正确性怀疑，大概率是认为 $i$ 后面的 $b$ 时间无法密排，但此时无法密排的一段中 $a$ 时间一定是密排的（并且 $\max$ 会选到后一种方案）。

然后运用临项交换法的思路，可以推出

$$\begin{align}\max(a_y, b_x)-a_y-b_x &< \max(b_y, a_x)-a_x-b_y\\-\min(a_y, b_x) &< -\min(b_y, a_x)\\\min(a_x, b_y) &< \min(b_x, a_y)\end{align} $$

你可能会认为：直接放入 sort 的 cmp 中即可。但这会引发 UB，因为它不满足传递性，因此也不是一个全序关系。

此时我们需要构造一种满足 $\min(a_x, b_y) < \min(b_x, a_y)$ 的全序比较关系，将数据分为两类：

• $a_i < b_i$，按 $a_i$ 从小到大排序。
• $a_i \geqslant b_i$，按 $b_i$ 从大到小排序。