P10207 [JOI 2024 Final] 马拉松比赛 2 题解

Perta · 2024-03-20 09:32:46 · 题解

拿球的总时间是固定的，这个可以不考虑。

一个朴素的想法是，设 f_{S,i} 表示已经拿了 S 的球，现在在第 i 个球的位置所用的最短时间，转移是朴素的，可以获得 24 分。

我们可以发现一个比较显然的性质：位于 G 同一侧的球，离 G 较远的球必然先于较近的被拿。

那么实际上有效状态 S 只有 O(N^2) 个。设 f_{l,r,0/1} 表示拿了编号范围 [1,l)\cup(r,N] 的球，现在在第 l/r 个球的位置所需的最短时间，转移是朴素的。初始有 f_{1,N,0}=\lvert S-X_1\rvert,f_{1,N,1}=\lvert S-X_N\rvert。

设 G 左右两边的小球编号分别为 p_1,p_2（也可能只有一个），所需时间为 \min(f_{p_1,p_1,0}+(N+1)\lvert X_{p_1}-G\rvert,f_{p_2,p_2,0}+(N+1)\lvert X_{p_2}-G\rvert)。

对于多次询问，我们不妨直接设另一个数组 g，含义与 f 相同，初始有 f_{1,N,0}=g_{1,N,1}=0，那么所需时间为 \min(\lvert S-X_1\rvert+f_{p_1,p_1,0}+(N+1)\lvert X_{p_1}-G\rvert,\lvert S-X_N\rvert+g_{p_2,p_2,0}+(N+1)\lvert X_{p_2}-G\rvert)。f,g 可以预处理，时间复杂度为 O(N^2+Q)（Q 带不带 \log 都行）。

看起来似乎没有优化空间了？

注意到 T\leq5\times10^5。若去重后不同的球的位置有 n 个，在最理想的情况下，所需的时间也得是 2+3+4+\cdots+(n+1)（每捡一个球后走一米）。若理恵能完赛，至少要求 \frac{(n+2)(n+1)}{2}-1\leq T，也就是说 n\geq10^3 时答案全是 No。

去重不影响我们的算法正确性，时间复杂度 O(n^2+Q)（最后记得加上拿球的总时间 N）。

Code，你怎么知道我 Q 带了个 \log。