CF1299C-Water Balance

题目:

题目描述:

There are $n$ water tanks in a row, $i$ -th of them contains $a_i$ 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$ .

输入格式:

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

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ( $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.

输出格式:

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 $a_i$ does not exceed $10^{-9}$ .

Formally, let your answer be $a_1, a_2, \dots, a_n$ , and the jury’s answer be $b_1, b_2, \dots, b_n$ . Your answer is accepted if and only if $\frac{|a_i - b_i|}{\max{(1, |b_i|)}} \le 10^{-9}$ for each $i$ .

样例:

样例输入 1:

1
2

4
7 5 5 7

样例输出 1:

1
2
3
4

5.666666667
5.666666667
5.666666667
7.000000000

样例输入 2:

1
2

5
7 8 8 10 12

样例输出 2:

1
2
3
4
5

7.000000000
8.000000000
8.000000000
10.000000000
12.000000000

样例输入 3:

1
2

10
3 9 5 5 1 7 5 3 8 7

样例输出 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

3.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
5.000000000
7.500000000
7.500000000

思路:

实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include "ybwhead/ios.h"
int l, r;
const int maxn = 1e6 + 10;
long long sum[maxn];
int q[maxn];
int main()
{
    // int TTT;
    // yin >> TTT;
    // while (TTT--)
    {
        int n;
        yin >> n;
        for (int i = 1; i <= n; i++)
        {
            int x;
            yin >> x;
            sum[i] = sum[i - 1] + x;
        }
        l = r = 0;
        for (int i = 1; i <= n; i++)
        {
            while (l < r && (sum[i] - sum[q[r]]) * (q[r] - q[r - 1]) <= (sum[q[r]] - sum[q[r - 1]]) * (i - q[r]))
                r--;
            q[++r] = i;
        }
        for (int i = 1; i <= r; i++)
        {
            double xx = (double)(sum[q[i]] - sum[q[i - 1]]) / (q[i] - q[i - 1]);
            for (int j = q[i - 1] + 1; j <= q[i]; j++)
                printf("%.9lf\n", xx);
        }
    }
    return 0;
}