分数: 700 点
问题陈述
有 N 数轴上的史莱姆,以及 i-第一个史莱姆位于坐标处 A_i。 所有这些坐标都是不同的。 每个史莱姆的重量为 1。 另外,你会得到一个整数 K.
首先,您将选择 K 粘液并将其他人从数轴上移除。 那么,从时间 0,选定的史莱姆将按如下方式移动:
- 每个史莱姆的运动:让 R 是坐标大于其自身的史莱姆的总重量,并且 L 是坐标处小于其自身的史莱姆的总重量。 然后,它以速度移动 R-L。请注意,速度可以为负值。也就是说,如果 R-L<0.
当两个或多个史莱姆同时到达同一坐标时,它们会合并。 合并后的史莱姆的重量是合并前史莱姆的重量之和。 合并后的史莱姆将按照与上述相同的规则移动。
的 K 史莱姆将继续合并,直到只剩下一个史莱姆。 让 t 是这个单一史莱姆诞生的时刻。 您的目标是选择 K 史莱姆这样 t 已最大化。 找到最大值 t.
约束
- 2 \leq K \leq N \leq 250000
- 0 = A_1 < A_2 < \cdots < A_N \leq 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N K A_1 A_2 \cdots A_N
输出
将答案打印为实数。 如果绝对误差或相对误差最多为,则认为是正确的 10^{-9}.
示例输入 1
3 2 0 1 2
示例输出 1
1.00000000000000000000
- 选择第一个和第二个史莱姆会导致 t=0.5.
- 选择第一个和第三个史莱姆会导致 t=1.
- 选择第二个和第三个史莱姆会导致 t=0.5.
因此,答案是 1.
示例输入 2
4 3 0 1 4 9
示例输出 2
2.83333333333333333333
如果您选择第 1 个、第 2 个和第 4 个史莱姆,则史莱姆的移动方式如下:
- 为了方便起见,请调用第 1 个、第 2 个和第 4 个史莱姆 X, Y,和 Z。
- 时间 0: X, Y,和 Z 开始以速度移动 +2, 0,和 -2。
- 时间 1/2: X 和 Y 在坐标处合并 1。合并后的粘液,称为 XY,开始以速度移动 1。另一方面, Z 位于坐标处 8 并继续以速度移动 -2.
- 时间 17/6: XY 和 Z 在坐标处合并 10/3。因此, t=17/6.
不可能使 t 大于 17/6,这就是答案。
示例输入 3
4 4 0 1 2 3
示例输出 3
0.50000000000000000000
示例输入 4
20 6 0 3441380 120768398 229897071 231209282 232046760 254924545 325399248 385631087 400098966 480503302 501372095 502644652 524585010 541761042 691400171 725009462 767549897 837806226 927396743
示例输出 4
135453315.33333333333333333333