P9604 [IOI2023] 超车

Alex_Wei · 2023-09-10 17:20:57 · 题解

P9604 [IOI2023] 超车

如果 x 被 y 堵住了，那么 x 的速度一定大于 y：如果 W_x > W_y，则存在 W_z > W_x 使得 y 被 z 堵住了，否则 y 不会把 x 堵住。简单地说，如果车辆 i 从 j - 1 到 j 的过程中并非全速行驶（t_{i, j} > e_{i, j}），那么存在 k 使得 k 到达 j - 1 的时间严格早于 i（t_{k, j - 1} < t_{i, j - 1}），且 k 到达 j 的时间严格晚于 i（e_{k, j} > e_{i, j}），这说明 k 的速度小于 i（W_k > W_i）。

这说明，在考虑 i 到达每个调度站的时间的时候，速度不小于 i 的车辆不产生影响：如果 i 被堵住，那么 i 所在的 “堵车集团” 一定是被它们当中速度最慢的车堵住的，可以认为 i 被这辆车堵住了，而如果这辆车的速度和 i 相同，那么可以认为 i 是在正常行驶，没有被堵住。因为我们只关心 N 到达调度站的时间，所以先忽略掉所有速度不小于 N 的车，即 W_i \leq X 的所有 i。以下设 W_i > X。

我们尝试对所有 0\leq i < N 和 0 \leq j < M 求出 t_{i, j}。首先有 t_{i, 0} = T_i。在 t_{*, j - 1}\to t_{*, j} 时，直接按照题目给出的方式暴力转移的时间复杂度是 \mathcal{O}(N ^ 2)，无法接受。按照 t_{i, j - 1} 从小到大枚举 i，同时维护所有 t_{k, j - 1} < t_{i, j - 1} 的 e_{k, j} 的最大值即可做到 \mathcal{O}(N\log N)。如果 t_{i, j - 1} 相同的 i 按照速度从快到慢枚举，则有先枚举的 i 先到达 j 的性质：后到达 j - 1 的车不会比先到达 j - 1 的车早到达 j，而同一时刻到达 j - 1 的车，排在前面的速度更快，更早到达 j。在这种枚举顺序下，我们可以认为 i 到达 j 的时间受到的限制是比它先枚举的 k 到达 j 的 实际时间 t_{k, j}，而非 期望时间 e_{k, j}（因为限制到 i 的 k 一定满足实际时间等于期望时间），也就是令 t_{i, j} \gets t_{i, j - 1} + W_i(S_j - S_{j - 1}) 之后，对 t_{*, j} 做 "前缀" \max。