A5170 | $幸运背包$

时间限制2s

内存限制1024MB

通过 / 提交0/0

题目描述

现在，公司内还剩下 $N$ 个周边商品。第 $i$ 个商品的重量为 $W_i$。 NoonMaple打算将剩下的商品分成 $D$ 个福袋一起出售。 他希望让每个福袋中商品重量总和的方差最小。 设每个福袋中商品重量的总和分别为 $x_1, x_2, \ldots, x_D$， 它们的平均值为 $\bar{x} = \frac{1}{D}(x_1 + x_2 + \cdots + x_D)$， 方差定义为 $V = \frac{1}{D}\displaystyle\sum_{i=1}^D (x_i - \bar{x})^2$。 请你求出将商品分配到各个福袋，使得每个福袋中商品重量总和的方差最小的情况下，这个最小方差的值。 可以存在空的福袋（此时该福袋中商品重量总和视为 $0$），但 **每个商品必须且仅能放入 $D$ 个福袋中的一个**。

输入以以下格式从标准输入读入。 > $N$ $D$ $W_1$ $W_2$ $\ldots$ $W_N$

输出将商品分配到各个福袋，使得每个福袋中商品重量总和的方差最小的情况下，这个最小方差的值。 当你的输出与真实值的绝对误差或相对误差不超过 $10^{-6}$ 时，将被判定为正确。

输入 #1

5 3
3 5 3 6 3

输出 #1

0.888888888888889

C++ 编辑器

输入

输出