3503. 平等分锅

单点时限: 2.0 sec

内存限制: 256 MB

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

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

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

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

输入格式

第一行包含两个整数 n, m。(1n500 000, nm108)
第二行包含 n 个整数,第 i 个整数表示第 ai。(1ai106)

输出格式

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

你的答案与正确答案的相对误差小于 106 即被视为正确。

样例

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 人解决,4 人已尝试。

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

9.9 EMB 奖励。

创建: 7 年,2 月前.

修改: 7 年前.

最后提交: 4 年,4 月前.

来源: EOJ Monthly 2018.3

题目标签