← 返回题目列表

AtCoder · past17_n

N. 软件更新

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

问题陈述

高桥要更新了 N 应用编号的应用 1,应用程序 2, \ldots和应用程序 N.
正在更新应用程序 i (1\leq i\leq N) 成本 T_i 时间单位。

Takahashi 可以选择要更新的应用程序的顺序。
开始时间 0,他的电脑按照指定的顺序一一更新应用程序。
正式来说,如果他让 i-th (1\leq i\leq N)要更新的应用程序是应用程序 p_i,计算机的行为如下:

  • 更新应用 p_k 从时间 (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}) 到时间 (T_{p_1}+T_{p_2}+\cdots+T_{p_{k-1}}+T_{p_k}).

他希望选择顺序,以便在检查更新进度时,可以尽可能正确地估计整个更新所需的总持续时间。

但是,在更新期间,他只能访问单个整数 k,这表明 k第次更新正在进行中。
如果他认识到 k- 第次更新正在进行中 t,他估计整个更新的持续时间是 f(t)=\frac{N}{k-0.5}\cdot t.
在此,当 i-th 更新开始,他认识到 i第次更新正在进行中。 具体来说,在某个时间 0 他认为 1-st 更新正在进行中; 当 i-th 更新完成并且 (i+1)第次更新开始,他认为 (i+1)-第更新是 正在进行中。

让 S\left(=\displaystyle\sum_{i=1}^N T_i\right) 是整个更新的总持续时间。 假设他估计整个更新的持续时间 t,这是一个随机实变量,选自 0 (含)至 t (独家)均匀随机。 找到最小期望值 \lvert f(t)-S\rvert 当他选择排列以最小化它时。

约束

  • 2\leq N\leq 18
  • 1\leq T_i\leq 10^6
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
T_1 T_2 \ldots T_N 

输出

打印期望值 \lvert f(t)-S\rvert 当他选择排列以最小化它时。
如果与真实值的绝对或相对误差最多为 10^{-6}.


示例输入 1

2
3 7

示例输出 1

3.066666666666667

整个更新的总持续时间为 S=3+7=10.
当他指定应用程序的更新顺序时 1\to 2,他的预计持续时间 如果他及时检查进度,则 f(t) 整个更新 t (0\leq t<10)是:

  • f(t)=\frac{2}{1-0.5}\cdot t=4t if 0\leq t< 3;
  • f(t)=\frac{2}{2-0.5}\cdot t=\frac{4}{3}t if 3\leq t< 10.

当 t 从范围中选择 0\leq t\lt 10 均匀随机,期望值 \lvert f(t)-S\rvert is \frac{46}{15}=3.066\cdots, 这是可能的最小值。


示例输入 2

3
3 1 1

示例输出 2

1.420000000000000

的预期值 \lvert f(t)-S\rvert 为最小值 如果他指定应用程序的更新顺序是 1\to 3\to 2.