← 返回题目列表

AtCoder · abc341_g

G. 最高比率

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

分数: 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