A90528.「USACO 2024 US Open Platinum」Activating Robots

题目译自 USACO 2024 US Open Contest, Platinum Problem 3. Activating Robots

你和一个机器人最初位于周长为 $L\ (1\le L\le 10^9)$ 的圆上的 $0$ 点。你可以以每秒 $1$ 个单位的速度沿圆逆时针或顺时针移动。本题中的所有移动都是连续的。

你的目标是放置恰好 $R-1$ 个机器人，使得最后每两个连续的机器人之间的间距为 $L/R$（$2\le R\le 20$，$R$ 整除 $L$）。有 $N\ (1\le N\le 10^5)$ 个激活点，其中第 $i$ 个激活点位于离 $0$ 点逆时针方向的 $a_i\ (0\le a_i<L)$ 处。如果你当前位于某个激活点，则可以在该点瞬间放置一个机器人。所有机器人（包括原机器人）以每 $K\ (1\le K\le 10^6)$ 秒 $1$ 个单位的速度逆时针移动。

计算实现目标所需的最短时间。

第一行四个整数 $L,R,N,K$。

第二行 $N$ 个整数 $a_1,a_2,\ldots,a_N$。

输出实现目标的最短时间。

• 测试点 5-6：$R=2$
• 测试点 7-12：$R\le 10,N\le 80$
• 测试点 13-20：$R\le 16$
• 测试点 21-24：无附加限制

供题：Benjamin Qi