题目名称 | 4068. [USACO24 Open Platinum]Activating Robots |
---|---|
输入输出 | activating_robots.in/out |
难度等级 | ★★★☆ |
时间限制 | 2000 ms (2 s) |
内存限制 | 256 MiB |
测试数据 | 24 |
题目来源 | yuan 于2024-11-22加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:1, 提交:1, 通过率:100% | ||||
xxz | 100 | 8.249 s | 182.05 MiB | C++ |
本题关联比赛 | |||
2024.12.21 |
关于 Activating Robots 的近10条评论(全部评论) |
---|
activating_robots.in
输出文件:activating_robots.out
简单对比你和一个机器人初始时位于周长为 $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$ 单位的速度逆时针移动($1\le K\le 10^6$)。
计算达到目标所需要的最小时间。
输入的第一行包含 $L$,$R$,$N$ 和 $K$。
第二行包含 $N$ 个空格分隔的整数 $a_1,a_2,\ldots,a_N$。
输出达到目标所需要的最小时间。
10 2 1 2 6
22
10 2 1 2 7
4
样例解释 1
我们可以通过顺时针移动在 $4$ 秒内到达点 $6$ 的激活点。此时,初始的机器人将位于点 $2$。再等待 $18$ 秒直到初始机器人位于点 $1$。现在我们可以放置一个机器人以立即获胜。
样例解释 2
我们可以通过顺时针移动在 $3$ 秒内到达点 $7$ 的激活点。此时,初始的机器人将位于点 $1.5$。再等待一秒直到初始机器人位于点 $2$。现在我们可以放置一个机器人以立即获胜。
32 4 5 2 0 23 12 5 11
48
24 3 1 2 16
48
- 测试点 $5-6$:$R=2$。
- 测试点 $7-12$:$R\le 10,N\le 80$。
- 测试点 $13-20$:$R\le 16$。
- 测试点 $21-24$:没有额外限制。