[CF1299C] Water Balance

Description

给定一个序列，可以进行无限次操作，每次选定一个区间，将该区间内的所有数变成区间的平均数，求操作后字典序最小的序列。

Solution

考虑单调栈，每次如果栈顶比带入栈元素高就暴力弹栈，将被弹出的元素和带入栈的元素合并。

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int n;
int a[N];

struct Item 
{
    double val;
    int siz;
    bool operator < (const Item &x)
    {
        return val<x.val;
    }
    Item operator + (const Item &x)
    {
        Item res;
        res.siz=siz+x.siz;
        res.val=(val*siz+x.val*x.siz)/res.siz;
        return res;
    }
} sta[N];

int top;

signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        Item tmp={a[i],1};
        while(top && tmp<sta[top])
        {
            tmp=tmp+sta[top];
            --top;
        }
        sta[++top]=tmp;
    }
    for(int i=1;i<=top;i++)
    {
        for(int j=1;j<=sta[i].siz;j++)
        {
            printf("%.8lf
",sta[i].val);
        }
    }
    return 0;
}