题解：P6243 [USACO06OPEN] The Milk Queue G

· · 题解

先找出总时间的表达式：

\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) 的全序比较关系，将数据分为两类：