自动搬运

查看原文

来自洛谷，原作者为

	Perta broken tower

搬运于2025-08-24 22:55:45，当前版本为作者最后更新于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$。