AT_abc332_e [ABC332E] Lucky bag

题目描述

AtCoder 社在在线商店销售周边商品。

现在，公司内还剩下 $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}$ 时，将被判定为正确。

输入输出样例 #1

输入 #1

5 3
3 5 3 6 3

输出 #1

0.888888888888889

说明/提示

限制条件

• $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 翻译