A6142. 「USACO 2024 US Open Platinum」Activating Robots
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2024 US Open Contest, Platinum](http://usaco.org/index.php?page=open24results) Problem 3. [Activating Robots](http://usaco.org/index.php?page=viewproblem2&cpid=1430)**
你和一个机器人最初位于周长为 $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\ (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$。
第二行 $N$ 个整数 $a_1,a_2,\ldots,a_N$。
输出格式
输出实现目标的最短时间。
输入输出样例
输入 #1
10 2 1 2 6
输出 #1
22
输入 #2
10 2 1 2 7
输出 #2
4
输入 #3
32 4 5 2 0 23 12 5 11
输出 #3
48
输入 #4
24 3 1 2 16
输出 #4
48
说明/提示
- 测试点 5-6：$R=2$
- 测试点 7-12：$R\le 10,N\le 80$
- 测试点 13-20：$R\le 16$
- 测试点 21-24：无附加限制
供题：Benjamin Qi
- 测试点 7-12：$R\le 10,N\le 80$
- 测试点 13-20：$R\le 16$
- 测试点 21-24：无附加限制
供题：Benjamin Qi