分数: 525 点
问题陈述
AtCoder Inc. 在其网站上销售商品 网上商店.
有 N 公司剩余物品。 的重量 i- 第一项 (1\leq i\leq N) is W_i.
高桥将出售这些物品 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,
这是最小值。
请注意,多个物品可能具有相同的重量, 并且每件物品都必须放在其中一个幸运袋中。