← 返回题目列表

Codeforces · 1299/C

C. 水平衡

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

一排有 $$$n$$$ 个水箱,其中 $$$i$$$ 个水箱包含 $$$a_i$$$ 升水。坦克从左到右编号为 $$$1$$$ 到 $$$n$$$。

您可以执行以下操作:选择某个子段 $$$[l, r]$$$ ($$$1\le l \le r \le n$$$),然后均匀地重新分配水箱 $$$l, l+1, \dots, r$$$ 中的水。换句话说,将 $$$a_l, a_{l+1}, \dots, a_r$$$ 替换为 $$$\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}$$$。例如,如果对于容量 $$$[1, 3, 6, 7]$$$,您选择 $$$l = 2, r = 3$$$,则新的水量将为 $$$[1, 4.5, 4.5, 7]$$$。您可以多次执行此操作。

你能得到的按字典顺序排列的最小的水体积序列是多少?

提醒一下:

序列 $$$a$$$ 按字典顺序小于相同长度的序列 $$$b$$$ 当且仅当以下条件成立:在 $$$a$$$ 和 $$$b$$$ 不同的第一个(最左边)位置,序列 $$$a$$$ 的元素比 $$$b$$$ 中的相应元素小。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^6$$$) — 水箱的数量。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 水箱中的初始水量,以升为单位。

由于输入较大,不建议将输入读取为双倍。

输出

打印你能得到的按字典顺序排列的最小序列。在第 $$$i$$$ 行中打印第 $$$i$$$ 水箱中的最终水量。

如果每个 $$$a_i$$$ 的绝对或相对误差不超过 $$$10^{-9}$$$,则认为您的答案是正确的。

正式来说,让您的答案为 $$$a_1, a_2, \dots, a_n$$$,陪审团的答案为 $$$b_1, b_2, \dots, b_n$$$。当且仅当每个 $$$i$$$ $$$\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$$$ 时,您的答案才会被接受。

示例

输入 #1

4
7 5 5 7

输出 #1

5.666666667
5.666666667
5.666666667
7.000000000

输入 #2

5
7 8 8 10 12

输出 #2

7.000000000
8.000000000
8.000000000
10.000000000
12.000000000

输入 #3

10
3 9 5 5 1 7 5 3 8 7

输出 #3

3.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
7.500000000
7.500000000

注意

在第一个示例中,您可以通过对子段 $$$[1, 3]$$$ 进行运算来获取序列。

在第二个示例中,您无法获得任何字典顺序较小的序列。