3503. 平等分锅

单点时限: 2.0 sec

内存限制: 256 MB

根据老大的指示,EOJ 需要增加一系列 $excit_{ing}$ 的功能,管理员们将他们的能力都量化为了正整数,现在如何合理分锅成为了一个大难题。

具体地说,一共有 $m$ 个功能需要被实现,一共有 $n$ 个管理员,第 $i$ 个管理员的能力是 $a_i$。由于时间紧迫,管理员们必须在规定的时间内完成,当第 $i$ 个管理员被分配了 $b_i$ 个功能时,我们称这 $b_i$ 个功能的实现程度为 $\frac{a_i}{b_i}$。

为了防止让 EOJ 看上去更统一,我们希望所有功能的实现度的方差尽可能的小。

注意:所有功能都必须被实现。

输入格式

第一行包含两个整数 $n$, $m$。($1 \leq n \leq 500~000$, $n \leq m \leq 10^8$)
第二行包含 $n$ 个整数,第 $i$ 个整数表示第 $a_i$。($1 \leq a_i \leq 10^6$)

输出格式

输出一个浮点数,表示所有题目实现度的方差的最小值。

你的答案与正确答案的相对误差小于 $10^{-6}$ 即被视为正确。

样例

Input
3 6
1 2 3
Output
0.000000000000
Input
5 10
5 6 7 8 9
Output
0.400000000000
Input
6 6
1 1 4 5 1 4
Output
2.888888888889

1 人解决,3 人已尝试。

1 份提交通过,共有 19 份提交。

9.9 EMB 奖励。

创建: 2 年,6 月前.

修改: 2 年,4 月前.

最后提交: 1 年,10 月前.

来源: EOJ Monthly 2018.3

题目标签