分数: 575 点
问题陈述
给你一个序列 A=(A_1,A_2,\ldots,A_N) 长度 N.
对于每个 k=1,2,\ldots,N,解决以下问题:
- 找到最大可能的平均值 k-th 至 r序列的第一项 A 选择整数时 r 这样 k\leq r\leq N.
这里,平均值 k-th 至 r序列的第一项 A 定义为 \frac{1}{r-k+1}\displaystyle\sum_{i=k}^r A_i.
约束
- 1\leq N\leq 2\times 10^5
- 1\leq A_i\leq 10^6
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N
输出
打印 N 行。
的 i第行 (1\leq i\leq N) 应包含问题的答案 k=i.
如果对于每一行,打印值与真实值的绝对或相对误差最多为,则您的输出将被视为正确 10^{-6}.
示例输入 1
5 1 1 4 5 3
示例输出 1
2.80000000 3.33333333 4.50000000 5.00000000 3.00000000
对于 k=1,可能的选择 r 是 r=1,2,3,4,5,每个的平均值为:
- \frac{1}{1}=1
- \frac{1}{2}(1+1)=1
- \frac{1}{3}(1+1+4)=2
- \frac{1}{4}(1+1+4+5)=2.75
- \frac{1}{5}(1+1+4+5+3)=2.8
因此,当 r=5,以及答案 k=1 is 2.8.
同样,对于 k=2,3,4,5,达到最大值时 r=4,4,4,5,分别为 \frac{10}{3}=3.333\ldots, \frac{9}{2}=4.5, \frac{5}{1}=5, \frac{3}{1}=3.
示例输入 2
3 999999 1 1000000
示例输出 2
999999.00000000 500000.50000000 1000000.00000000