← 返回比赛

已结束【提高组】GESP“飞翔杯”第一届季度赛

← 上一题下一题 →

A4675 | $扫雷$

来源官方 / 2024

时间限制1s

内存限制512MB

通过 / 提交0/0

题目描述

时间限制: 1S 空间限制: 512mb 样例文件: Mine 在神秘路上，小 O 发现这里隐藏了一排地雷，从左到右第 $i$ 个地雷的危险系数为 $a_i$。现在小 O 在位置 $k$ 上，他发现他的危险值取决于以位置 $k$ 开头的一段区间的危险系数最大平均值，即以 $k$ 开头的后缀的所有非空前缀的最大平均值。 由于小 O 被外星人抓走了，可能会随机降落在某一个格子，所以希望你对每个位置 $k (1 \le k \le n)$，计算其危险系数。： $$ \max{\left(\frac{\sum^{j}_{i=k}a_i}{j - i + 1}\right)} (k \le j \le n) $$

输入格式

第一行，一个正整数 $n$ 表示格子数量。 第二行，$n$ 个正整数，表示危险系数 $a_i$。

输出格式

总共 $n$ 行，第 $i$ 行一个实数，表示危险系数，绝对误差或相对误差不超过 $10^{-6}$ 即可判断为正确。

输入输出样例

输入 #1

5
1 1 4 5 3

输出 #1

输入 #2

3
999999 1 1000000

输出 #2

999999.00000000
500000.50000000
1000000.00000000

输入 #3

见选手目录下的 mine/mine3.in 与 mine/mine3.ans。

该组样例满足数据范围中描述的测试点 4 的限制。

输出 #3

对于所有的测试数据，保证： - $1\le n\le 5\times 10^5$； - $1\le a_i\le 10^9$。 测试点编号$n\le$特殊性质$1\sim 3$$300$无$4\sim 6$$5000$无$7\sim 9$$5\times 10^4$无$10,11$$10^5$无$12,13$$2\times 10^5$无$14$$5\times 10^5$A$15$$5\times 10^5$B$16$$5\times 10^5$C$17$$5\times 10^5$D$18$$5\times 10^5$E$19$$5\times 10^5$F$20$$5\times 10^5$无 - 特殊性质 A：$a_i$ 全相等； - 特殊性质 B：$a_i$ 单调不降； - 特殊性质 C：$a_i$ 单调不增； - 特殊性质 D：$a_i\le 1$； - 特殊性质 E：$a_i\le 2$； - 特殊性质 F：$a_i\le 5$。

C++ 编辑器

输入

输出