本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2025-10-11 16:37:13

:::::info[题目基本信息] 考察：动态规划 DP（$3300$）。
题目简介：
给定一个长度为 $m$ 的环，上面有编号从 $1$ 到 $m$ 的一些位置，一开始有 $n$ 个人站在 $n$ 个位置上，然后每个人会选定一个方向走 $p$ 步，求在每个位置都被至少一个人走到的基础上 $p$ 的最小值。
数据范围：

• $1\le m\le 10^9$
• $1\le n\le 10^5$
• $\forall i\in[1,n],1\le a_i\le m$

时间限制：1.5s。
空间限制：250MB。
::::: 首先注意到 $p$ 是满足单调性的，可二分答案，然后问题转化为判定 $p$ 是否合法。
放弃若干方法后，我们考虑 DP，设 $f_{i,j}$ 为考虑到第 $i$ 个人时是否能到达位置 $j$，但是每一个状态只存一个 bool 太浪费了，所以我们改设 $f_i$ 表示考虑到第 $i$ 个人时能到达的最远位置。
在推导状态转移方程前，还有一件事需要解决，那就是现在的 DP 是有后效性的，这是因为原问题是在环上做，我们考虑断环为链，但是还不能简单倍长，这样的话求出的 DP 数组就会被上一次求出的答案影响，所以我们要好好思考如何断环为链。
注意到答案下界是 $\displaystyle\max(\max_{i=1}^{n-1}a_{i+1}-a_i,a_1+m-a_n)$，如果大于等于这个值我们直接全部向一个方向走即可，我们只需要验证小于这个值的答案是否合法。
在这时，我们一定会有两个人之间不可互相走到对方的位置，我们在这里断开就不会影响答案了，我们将断开后的这条链重编号编为 $\{b_n\}$（钦定 $b_1=0$）。
这时我们就可以推状态转移方程了，我们分第 $1$ 个人（重编号后）往左或往右走分类讨论：

• 往左：这时初始条件为 $f_1=0$，最后如果 $f_n\ge m-p-1$ 则合法。
• 往右：这时第 $2$ 个人一定往左，因为 $n$ 填不满 $1$ 和 $n$ 之间的空，初始条件为 $f_2=\max(b_2,p)$，最后如果 $f_n\ge\min(m-1,m+b_2-p-1)$（实际上 $b_2$ 对应 $m-1$，$p$ 对应 $m+b_2-p-1$，但是若 $b_2$ 大，则 $m-1$ 小，所以可以在代码中简写）。

现在我们只差状态转移方程，开始分类讨论：

• 如果这一位向右走：
  此时上一位（也可能是上上位，下同）必定向右走填满了这两位中间的空隙，那么转移前提条件为 $f_{i-1}\ge b_i-1$，转移方程为 $f_i\leftarrow\max(f_i,b_i+p-1)$。
• 如果这一位向左走：
  此时上一位不一定往哪走，继续分类讨论：
  • 如果上一位向左走：
    此时上一位一定填到了这一位能填到的位置，转移前提条件为 $f_{i-1}\ge b_i-p-1$，转移为 $f_i\leftarrow\max(f_i,b_i)$。
  • 如果上一位向右走：
    此时仍需要分上一位是否填到了这一位分类讨论：
    • 如果没填到这一位：与上一位向左走转移相同。
    • 如果填到了这一位：
      虽然填到了这一位，但是不能直接转移，因为不一定与前面连续，所以我们需要从 $f_{i-2}$ 转移，前提条件为 $f_{i-2}\ge b_i-p-1$，转移为 $f_i=\max(f_i,b_{i-1}+p)$。
      同时由于有不连续转移，所以还有转移 $f_i\leftarrow\max(f_i,f_{i-1})$。

然后，我们就做完了这道题。
时间复杂度为 $\Theta(n\log m+n\log n)$，空间复杂度为 $\Theta(n)$。

code