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;
}