CF713E Sonya Partymaker 题解

zrl123456 · 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