#2392. 「JOISC 2017 Day 1」烟花棒

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

题目译自 JOISC 2017 Day1 T3「手持ち花火 / Sparklers

JOISC17D1T3.md.png

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

3 2 50
0
200
300

样例输出 1

2

样例解释 1

开始时, 1 号向右, 2 号向左, 3 号向左。
50 秒后, 2 号传火给 1 我真的不是黑魂玩家。随后, 1 号和 3 号继续移动。
又过了 25 秒, 1 号传火给 3 号。

样例输入 2

3 2 10
0
200
300

样例输出 2

8

样例解释 2

开始时, 1 号向右, 2 号向右, 3 号向左。
3 秒后, 2 号停止移动。
又过了 6.5 秒, 3 号到达 2 号所在位置, 3 号停止移动。
又过了 0.5 秒, 2 号传火给 3 号。
又过了 9 秒, 3 号传火给 1 号。

样例输入 3

20 6 1
0
2
13
27
35
46
63
74
80
88
100
101
109
110
119
138
139
154
172
192

样例输出 3

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\} 单调递增。