P9579 题解（2023 激励计划评分 8）

Coffee_zzz · 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 即可。