自动搬运

查看原文

来自洛谷，原作者为

	Coffee_zzz 沉覆z

搬运于2025-08-24 22:49:47，当前版本为作者最后更新于2023-08-27 09:56:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

另一种不是 dp 的做法。

以下把 $a_i,b_i$ 看成一个区间。

首先记录数组 $a$ 和数组 $b$ 中的最大值 $m$，发现 $a\lt b$ 的区间没有用，因为移动到 $m$ 的过程中一定会满足这些要求，那我们就不管 $a \lt b$ 的区间，把所有满足 $a \gt b$ 的区间以 $a_i$ 为第一关键字从大到小排序。

我们首先把相交的区间都合并，然后枚举每个区间 $i$，下标大于 $i$ 的区间都用先走到 $a_i$ 再走回 $b_i$ 最后再走到 $a_i$ 的方法满足，下标小于等于 $i$ 的区间都从 $m$ 走回来，最后给所有可能的答案取 $\min$ 即可。