AT_abc332_e [ABC332E] Lucky bag

AtCoder 社在[在线商店](https://suzuri.jp/AtCoder/home)销售周边商品。 现在，公司内还剩下 $N$ 个周边商品。第 $i$ 个商品的重量为 $W_i$。 高桥君打算将剩下的商品分成 $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}$ 时，将被判定为正确。

## 限制条件 - $2 \leq D \leq N \leq 15$ - $1 \leq W_i \leq 10^8$ - 所有输入均为整数 ## 样例解释 1 将第 $1$、$3$ 个商品放入第 $1$ 个福袋，将第 $2$、$5$ 个商品放入第 $2$ 个福袋，将第 $4$ 个商品放入第 $3$ 个福袋，则各福袋中商品重量总和分别为 $6, 8, 6$。此时，平均值为 $\frac{1}{3}(6+8+6)=\frac{20}{3}$，方差为 $\frac{1}{3}\left\{\left(6-\frac{20}{3}\right)^2+\left(8-\frac{20}{3}\right)^2+\left(6-\frac{20}{3}\right)^2\right\}=\frac{8}{9}=0.888888\ldots$，这是最小值。 请注意，可能存在多个重量相同的商品，并且每个商品必须被分配到某个福袋。 由 ChatGPT 4.1 翻译