← 返回题目列表

AtCoder · past202306_n

N. 度数分布

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

问题陈述

有 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}.