← 返回题目列表

AtCoder · abc332_e

H. 福袋

中文机器翻译题面 查看原题

分数: 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, 这是最小值。

请注意,多个物品可能具有相同的重量, 并且每件物品都必须放在其中一个幸运袋中。