← 返回题目列表

AtCoder · awtf2024_a

A. 移动史莱姆

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

分数: 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