← 返回题目列表

Codeforces · 2055/D

D. 稻草人

中文机器翻译题面 查看原题

在佛罗里达男子的橘子园里,他又收到了一封由乌鸦寄来的垃圾邮件。当然,他会以最不方便的方式将其寄回。

一只乌鸦坐在数轴的 $$$0$$$ 位置。沿着数轴,在整数坐标 $$$a_1, a_2, \ldots, a_n$$$ 处有 $$$n$$$ 稻草人。这些稻草人被施了魔法,可以让它们以每秒 $$$1$$$ 单位的速度左右移动。

乌鸦害怕稻草人,并且希望与位于其或其之前的最近的稻草人保持至少 $$$k$$$ 的距离。为此,乌鸦使用其传送能力如下:

- 令 $$$x$$$ 为乌鸦的当前位置,并令 $$$y$$$ 为稻草人的最大位置,使得 $$$y \le x$$$。如果$$$x - y < k$$$,意味着稻草人太近,乌鸦将立即传送到位置$$$y + k$$$。

这种传送是即时且持续发生的。乌鸦会不断检查位于他或其左侧的稻草人,并在稻草人距离太近时进行传送(这可能会在非整数时间发生)。请注意,除了这种传送能力之外,乌鸦不会自行移动。

你的任务是确定让乌鸦传送到大于或等于 $$$\ell$$$ 的位置所需的最短时间,假设稻草人以最佳方式移动以允许乌鸦到达目标。为了方便起见,要求你输出乌鸦到达目标位置$$$\ell$$$所需最短时间的两倍。可以证明这个值永远是整数。

请注意,稻草人可以随时启动、停止或改变方向(可能在非整数时间)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n, k, \ell$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq \ell \leq 10^8$$$)——分别是稻草人的数量、传送距离和乌鸦的目标位置。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \leq a_1 \leq a_2 \leq \ldots \leq a_n \leq \ell$$$) — $$$n$$$ 稻草人的初始位置。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数,表示乌鸦传送到大于或等于 $$$\ell$$$ 的位置所需的最短时间的两倍。

示例

输入 #1

9
1 3 5
0
3 2 5
2 5 5
1 10 10
10
10 1 10
0 1 2 3 4 5 6 7 8 9
2 1 2
0 0
2 1 2
0 2
2 1 3
0 2
2 2 4
1 1
9 12 54
3 3 8 24 25 27 29 34 53

输出 #1

4
5
20
0
2
1
2
2
7

注意

在第一个测试用例中,由于位置 $$$0$$$ 处有稻草人,乌鸦立即传送到位置 $$$3$$$。然后,这个稻草人可能会移动到位置 $$$2$$$,导致乌鸦连续从位置 $$$3$$$ 移动到位置 $$$5$$$,在 $$$2$$$ 秒内完成行程。因此,输出为$$$4$$$。

在第二个测试用例中,稻草人$$$1$$$和稻草人$$$2$$$可以在$$$2$$$秒内分别移动到位置$$$0$$$和$$$3$$$,而稻草人$$$3$$$保持在位置$$$5$$$。由于稻草人 $$$1$$$,乌鸦传送到位置 $$$2$$$。然后,稻草人 $$$1$$$ 向右移动,而稻草人 $$$2$$$ 和稻草人 $$$3$$$ 向左移动 $$$0.5$$$ 秒。这会导致乌鸦不断地从位置 $$$2$$$ 移动到位置 $$$2.5$$$,因为稻草人 $$$1$$$ 从位置 $$$0$$$ 向右移动。半秒后,稻草人将位于 $$$0.5、2.5、4.5$$$ 位置。稻草人 $$$2$$$ 现在位于 $$$2.5$$$ 位置,导致乌鸦立即传送到位置 $$$4.5$$$,而位置 $$$4.5$$$ 的稻草人 $$$3$$$ 导致它立即传送到位置 $$$6.5$$$,这超过了 $$$\ell = 5$$$。因此,乌鸦只用了 $$$2.5$$$ 秒就完成了旅程,输出为 $$$5$$$。

可以证明,这些是两个测试用例的最小可能时间。