103324: [Atcoder]ABC332 E - Lucky bag

Problem Statement

AtCoder Inc. sells merchandise on its online shop.

There are $N$ items remaining in the company. The weight of the $i$-th item $(1\leq i\leq N)$ is $W_i$.

Takahashi will sell these items as $D$ lucky bags.
He wants to minimize the variance of the total weights of the items in the lucky bags.
Here, the variance is defined as $V=\frac{1}{D}\displaystyle\sum_{i=1}^D (x_i-\bar{x})^2$, where $x_1,x_2,\ldots,x_D$ are the total weights of the items in the lucky bags, and $\bar{x}=\frac{1}{D}(x_1+x_2+\cdots+x_D)$ is the average of $x_1,x_2,\ldots,x_D$.

Find the variance of the total weights of the items in the lucky bags when the items are divided to minimize this value.
It is acceptable to have empty lucky bags (in which case the total weight of the items in that bag is defined as $0$),
but each item must be in exactly one of the $D$ lucky bags.

Constraints

• $2 \leq D\leq N\leq 15$
• $1 \leq W_i\leq 10^8$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$ $D$
$W_1$ $W_2$ $\ldots$ $W_N$

Output

Print the variance of the total weights of the items in the lucky bags when the items are divided to minimize this value.
Your output will be considered correct if the absolute or relative error from the true value is at most $10^{-6}$.

Sample Input 1

5 3
3 5 3 6 3

Sample Output 1

0.888888888888889

If you put the first and third items in the first lucky bag, the second and fifth items in the second lucky bag, and the fourth item in the third lucky bag, the total weight of the items in the bags are $6$, $8$, and $6$, respectively.

Then, the average weight is $\frac{1}{3}(6+8+6)=\frac{20}{3}$,
and the variance is $\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$, which is the minimum.

Note that multiple items may have the same weight, and that each item must be in one of the lucky bags.

问题描述

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$个幸运袋中的一个。

约束条件

• $2 \leq D\leq N\leq 15$
• $1 \leq W_i\leq 10^8$
• 所有输入值为整数。

输入

输入从标准输入给出，如下所示：

$N$ $D$
$W_1$ $W_2$ $\ldots$ $W_N$

输出

当商品被分为最小化此值时，打印幸运袋内商品总重量的方差。 如果与真实值的绝对或相对误差不超过$10^{-6}$，则认为您的输出是正确的。

样例输入 1

5 3
3 5 3 6 3

样例输出 1

0.888888888888889

如果您将第一件和第三件商品放入第一个幸运袋， 将第二件和第五件商品放入第二个幸运袋， 将第四件商品放入第三个幸运袋， 则各袋内的商品总重量分别为$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$， 这是最小值。

请注意，多个商品可能具有相同的重量， 而且每件商品必须在一个幸运袋中。