E. Water Balance

Codeforces Round 618 (Div. 2) E. Water Balance

Description

There are n water tanks in a row, i-th of them contains ai liters of water. The tanks are numbered from 1 to n from left to right.

You can perform the following operation: choose some subsegment [l,r] ($1\le l \le r \le n$), and redistribute water in tanks $l, l+1, \dots, r$ evenly. In other words, replace each of $a_l, a_{l+1}, \dots, a_r$ by $\frac{a_l + a_{l+1} + \dots + a_r}{r-l+1}$. For example, if for volumes $[1, 3, 6, 7]$ you choose l=2,r=3, new volumes of water will be $[1,4.5,4.5,7]$. You can perform this operation any number of times.

What is the lexicographically smallest sequence of volumes of water that you can achieve?

As a reminder:

A sequence a is lexicographically smaller than a sequence b of the same length if and only if the following holds: in the first (leftmost) position where a and b differ, the sequence a has a smaller element than the corresponding element in b.

Input
The first line contains an integer n ($1 \le n \le 10^6$) — the number of water tanks.

The second line contains n integers a1,a2,…,an ($1 \le a_i \le 10^6$) — initial volumes of water in the water tanks, in liters.

Because of large input, reading input as doubles is not recommended.

Output
Print the lexicographically smallest sequence you can get. In the i-th line print the final volume of water in the i-th tank.

Your answer is considered correct if the absolute or relative error of each ai does not exceed $10^{-9}$.

Formally, let your answer be a1,a2,…,an, and the jury's answer be b1,b2,…,bn. Your answer is accepted if and only if $\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$ for each i.

Examples
input
4
7 5 5 7
output
5.666666667
5.666666667
5.666666667
7.000000000
input
5
7 8 8 10 12
output
7.000000000
8.000000000
8.000000000
10.000000000
12.000000000
input
10
3 9 5 5 1 7 5 3 8 7
output
3.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
7.500000000
7.500000000
Note
In the first sample, you can get the sequence by applying the operation for subsegment [1,3].

In the second sample, you can't get any lexicographically smaller sequence.

Problem solving

这道题的意思就是给你一个序列，你可以选择无数次任意区间[l,r]进行操作，就是把这个区间中的所有数变成这个区间的平均数。问你你能通过这个操作能达到的最小字典序的序列是什么。
要求字典序最小，所以越往前的越小，直接就想到了贪心。我写的时候，只是考虑了新加一个数的时候对他前面那一个数的影响，所以WA了。显然新加入一个数，可能对他前面所有的数造成影响。所以我们需要考虑的更多一些。

我们定义两个数组，p[i]第i组中数的和，q[i]代表第i组中数的个数。
每次考虑一个新的数，用while计算它能让本来的值变小的数的个数，期间还需要维护前i个数的和。
最后按照组输出即可。

Code

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
typedef long long ll;
inline ll read()
{
    ll   flag = 1, ans = 0;
    char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-')
            flag = 1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        ans = ans * 10 + c - '0';
        c   = getchar();
    }
    return ans * flag;
}//cin的通过代码是2324 ms，我加了快读是1325 ms，scanf/printf是1248 ms
ll a[maxn], p[maxn], q[maxn];
int main()
{
    ll n, x = 0, y = 0, pos = 0;
    scanf("%lld",&n);
    for (ll i = 1; i <= n; i++)
        scanf("%lld",&a[i]);
    for (ll i = 1; i <= n; i++)
    {
        x = a[i], y = 1;
        while (pos && p[pos] * y >= x * q[pos])//p[pos] * y >= x * q[pos]这一句是用来计算新考虑的这个数对前面是否有影响，如果小于，说明加上这个数会使前面的数都减小，所以加上
            x += p[pos], y += q[pos--];
        p[++pos] = x, q[pos] = y;
    }//计算出来总共pos组数，每组数有q[i]个
    for (ll i = 1; i <= pos; i++)
        for (ll j = 1; j <= q[i]; j++)
            printf("%.9lf\n", p[i] * 1.0 / q[i]);
    return 0;
}