AT_awtf2024_a.Moving Slimes

在数轴上有 $N$ 只史莱姆，第 $i$ 只史莱姆位于坐标 $A_i$。这些坐标互不相同。每只史莱姆的质量为 $1$。另外，给定一个整数 $K$。

你需要首先选择 $K$ 只史莱姆，并将未被选中的史莱姆从数轴上移除。之后，被选中的史莱姆从时刻 $0$ 开始按照以下规则移动：

• 每只史莱姆的移动方式如下：设自己右侧（坐标更大）所有史莱姆的质量总和为 $R$，左侧（坐标更小）所有史莱姆的质量总和为 $L$。则该史莱姆以速度 $R-L$ 移动。注意速度可以为负，即当 $R-L<0$ 时，史莱姆向数轴负方向移动。

当有两只及以上的史莱姆同时到达同一坐标时，它们会合体。合体后的史莱姆质量为合体前所有史莱姆质量之和。合体后的史莱姆也按照上述规则继续移动。

$K$ 只史莱姆会不断合体，最终只剩下一只史莱姆。该史莱姆诞生的瞬间记为时刻 $t$。你的目标是，合理选择 $K$ 只史莱姆，使得 $t$ 最大。请输出 $t$ 的最大值。

输入以如下格式从标准输入读入：

$N$ $K$ $A_1$ $A_2$ $\cdots$ $A_N$

请输出一个实数作为答案。如果你的答案与标准答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

限制条件

• $2 \leq K \leq N \leq 250000$
• $0 = A_1 < A_2 < \cdots < A_N \leq 10^9$
• 所有输入值均为整数

样例解释 1

• 选择第 $1$ 和第 $2$ 只史莱姆时，$t=0.5$。
• 选择第 $1$ 和第 $3$ 只史莱姆时，$t=1$。
• 选择第 $2$ 和第 $3$ 只史莱姆时，$t=0.5$。
  因此答案为 $1$。

样例解释 2

当选择第 $1,2,4$ 只史莱姆时，史莱姆的移动过程如下：

• 将第 $1,2,4$ 只史莱姆分别记为 $X,Y,Z$。
• 时刻 $0$：$X,Y,Z$ 分别以速度 $+2,0,-2$ 开始移动。
• 时刻 $1/2$：$X$ 和 $Y$ 在坐标 $1$ 处合体，合体后的史莱姆记为 $XY$，$XY$ 以速度 $1$ 继续移动，$Z$ 此时在坐标 $8$，速度仍为 $-2$。
• 时刻 $17/6$：$XY$ 和 $Z$ 在坐标 $10/3$ 处合体。
  因此 $t=17/6$。无法使 $t$ 更大，所以答案为 $17/6$。

由 ChatGPT 4.1 翻译