Lucky bag

题目描述

AtCoder Inc. 在其 在线商店 销售商品。 公司剩余 $N$ 件商品。 第 $i$ 件商品 $(1\leq i\leq N)$ 的重量为 $W_i$。 Takahashi 将把这些商品作为 $D$ 个福袋出售。
他希望最小化福袋中物品总重量的方差。
这里，方差定义为 $V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2$，其中 $x_1,x_2,\ldots,x_D$ 是各福袋中物品的总重量，$\bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D)$ 是 $x_1,x_2,\ldots,x_D$ 的平均值。 当物品被划分以使该值最小化时，求福袋中物品总重量的方差。
允许出现空的福袋（在这种情况下该福袋中物品的总重量定义为 $0$），
但 每件物品必须恰好放入这 $D$ 个福袋中的一个。

输入格式

输入由标准输入给出，格式如下： $N$ $D$ $W_1$ $W_2$ $\ldots$ $W_N$

输出格式

输出当物品被划分以使该值最小化时福袋中物品总重量的方差。
如果你的输出与真实值的绝对或相对误差至多为 $10^{-6}$，则认为是正确的。

5 3
3 5 3 6 3

0.888888888888889

提示

$2 \leq D\leq N\leq 15$ $1 \leq W_i\leq 10^8$ 所有输入值均为整数。如果你将第 1 件和第 3 件物品放在第一个福袋， 第 2 件和第 5 件物品放在第二个福袋， 第 4 件物品放在第三个福袋， 则各福袋中物品的总重量分别为 $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$， 这是最小值。 注意不同物品可能具有相同重量， 且每件物品必须放在某个福袋中。

标签: AtCoder|abc332E

来源

AtCoder|abc332E