问题陈述
有 N 实数 x_1,\ldots,x_N 之间 0 (含)和 M (独家)。
其中 N 号,已知有 C_k 之间的数字 k (含)和 k+1 (独家)对于 k=0,1,\ldots,M-1.
您好奇中位数和平均值之间的绝对差异有多大 x_1,\ldots,x_N 可以。
找到最大的 b 使得中位数和平均值之间的绝对差 x_1,\ldots,x_N 不能小于 b.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq C_k
- C_0+\ldots+C_{M-1}=N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
C_0 C_1 \ldots C_{M-1}
输出
打印答案。
如果真实答案的绝对或相对误差最多为,则您的输出将被视为正确 10^{-6}.
示例输入 1
3 3 0 1 2
示例输出 1
0.0
例如,当 x_1=1.5, x_2=2, x_3=2.5,这些数字的中位数和平均值都是 2,绝对差为 0.
由于绝对差不能小于 0,最大 b 使得中位数和平均值之间的绝对差不能小于 b is 0.
示例输入 2
4 5 2 1 0 0 1
示例输出 2
0.25
例如,当 x_1=4, x_2=1-2\times 10^{-100}, x_3=0, x_4=2-2\times 10^{-100},中位数是 1.5-2\times 10^{-100},含义是 1.75-10^{-100},绝对差为 0.25+10^{-100}.
正如这里所见,中位数和平均值之间的绝对差可能略大于 0.25,但我们可以证明它不能小于 0.25因此,答案是 0.25.
示例输入 3
10 10 1 0 0 0 0 0 0 0 0 9
示例输出 3
0.4
如果真实答案的绝对或相对误差最多为,则您的输出将被视为正确 10^{-6}.