#P17549. [JAG 2026 Summer Camp #2] Warp
[JAG 2026 Summer Camp #2] Warp
题目描述
有一个周长为 的圆,其中 为偶数。圆上的位置沿逆时针方向计量,用范围在 内的实数表示。
圆上有 个点,第 个点位于 。这些点的位置不一定互不相同。
开始时,你可以任选圆上的一个位置作为起点。
之后,你可以以每秒 单位的速度沿圆顺时针或逆时针移动。你可以随时改变移动方向,且改变方向不消耗时间。
此外,你可以随时使用魔法传送,次数不限。魔法传送不消耗时间,会把你移动到圆上与当前位置正对的位置。更精确地说,如果你位于 (),一次传送耗时 秒,传送后的位置为
$$\begin{cases} x+L/2 & (0\le x<L/2),\\ x-L/2 & (L/2\le x<L). \end{cases}$$只要你的位置与某个点的位置重合,就视为访问了该点。求将全部 个点都访问至少一次所需的最少时间,单位为秒。
输入格式
输入仅包含一组测试数据,格式如下。
N L
A_1 A_2 ... A_N
整数 表示圆上的点数()。偶数 表示圆的周长()。每个整数 满足 ,表示圆上第 个点的位置()。
输出格式
输出访问全部 个点所需的最少时间。可以证明答案为整数。
4 10
0 2 8 9
3
1 10
9
0
7 100
39 57 57 1 99 70 37
33
提示
在样例输入 1 中,可以按以下方式在 秒内访问全部 个点。
- 首先,从位置 出发,访问第 个点。
- 移动到位置 ,耗时 秒。
- 使用魔法传送到位置 ,耗时 秒,同时访问第 个点。
- 移动到位置 ,耗时 秒,同时访问第 个点。
- 移动到位置 ,耗时 秒,同时访问第 个点。