手持ち花火 (Sparklers)

#「JOISC 2017 Day 1」烟花棒 ## 题目描述 **题目译自 [JOISC 2017](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/index.html) Day1 T3「[手持ち花火](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d1.pdf)（[Sparklers](https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d1-en.pdf)）」**  有 $N$ 人站在一条数轴上。他们人手一个烟花，每人手中的烟花都恰好能燃烧 $T$ 秒。每个烟花只能被点燃一次。 $1$ 号站在原点，$i$ 号 $(1\le i\le N)$ 到 $1$ 号的距离为 $X_i$。保证 $X_1=0,$ $X_1, X_2, \dots, X_N$ **单调**递增（可能有人位置重叠）。 开始时， $K$ 号的烟花刚开始燃烧,，其他人的烟花均未点燃。他们的点火工具坏了，只能用燃着的烟花将未点燃的烟花点燃。当两人位置重叠且其中一人手中的烟花燃着时，另一人手中的烟花就可以被点燃。忽略点火所需时间。 求至少需要以多快的速度跑，才能点燃所有人的烟花（此时可能有些人的烟花已经熄灭了）。**速度必须是一个非负整数。** ## 输入格式 第一行有三个整数 $N,K,T$，用空格分隔。 在接下来的 $N$ 行中，第 $i$ 行 $(1\le i\le N)$ 有一个整数 $X_i$。 ## 输出格式 一个整数，表示要想点燃所有人的烟花，全程中最大速度的最小值。 ## 样例 #### 样例输入 1 ```plain 3 2 50 0 200 300 ``` #### 样例输出 1 ```plain 2 ``` #### 样例解释 1 开始时，$1$ 号向右，$2$ 号向左，$3$ 号向左。 $50$ 秒后，$2$ 号传火给 $1$ 号 ~~我真的不是黑魂玩家~~。随后，$1$ 号和 $3$ 号继续移动。 又过了 $25$ 秒，$1$ 号传火给 $3$ 号。 #### 样例输入 2 ```plain 3 2 10 0 200 300 ``` #### 样例输出 2 ```plain 8 ``` #### 样例解释 2 开始时，$1$ 号向右，$2$ 号向右，$3$ 号向左。 $3$ 秒后，$2$ 号停止移动。 又过了 $6.5$ 秒，$3$ 号到达 $2$ 号所在位置，$3$ 号停止移动。 又过了 $0.5$ 秒，$2$ 号传火给 $3$ 号。 又过了 $9$ 秒，$3$ 号传火给 $1$ 号。 #### 样例输入 3 ```plain 20 6 1 0 2 13 27 35 46 63 74 80 88 100 101 109 110 119 138 139 154 172 192 ``` #### 样例输出 3 ```plain 6 ``` ## 限制与提示 对于 $30\%$ 的数据，$N \le 20$。 对于 $50\%$ 的数据，$N \le 1000$。 对于 $100\%$ 的数据，$1\le K, N \le 10^5, 1\le T\le 10^9, 0\le X_i\le 10^9 (1\le i\le N), X_1 = 0, \{X_N\}$ 单调递增。 感谢 Planet6174 提供的翻译

[problemUrl]: https://atcoder.jp/contests/joisc2017/tasks/joisc2017_c