题目传送门

前置知识

单调栈

简化题意

给定一个长度为 \(n\) 的序列 \(a\)。对于所有的 \(l(1 \le l \le n)\)，均求出 \(\max\limits_{r=l}^{n} \{ \frac{\sum\limits_{i=l}^{r}a_{i}}{r-l+1} \}\)。

解法

令 \(sum_{i}=\sum\limits_{j=1}^{i}a_{j},P_{i}=(i,sum_{i})\)，则有 \(\begin{aligned} \max\limits_{r=l}^{n} \{ \frac{\sum\limits_{i=l}^{r}a_{i}}{r-l+1} \} =\max\limits_{r=l}^{n} \{ \frac{sum_{r}-sum_{l-1}}{r-l+1} \} =\max\limits_{r=l}^{n} \{ \frac{P_{r}.y-P_{l-1}.y}{P_{r}.x-P_{l-1}.x} \} \end{aligned}\)。

从后往前用单调栈维护斜率即可。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
ll a[200002],sum[200002],s[200002],x[200002],y[200002],top=0;
double ans[200002];
double work(ll u,ll v)
{
	return 1.0*(y[v]-y[u])/(x[v]-x[u]);
}
int main()
{
	ll n,i;
	cin>>n;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		sum[i]=sum[i-1]+a[i];
		x[i]=i;
		y[i]=sum[i];
	}
	top++;
	s[top]=n;
	for(i=n-1;i>=0;i--)
	{
		while(top>1&&work(i,s[top])<=work(s[top-1],s[top]))
		{
			top--;
		}
		ans[i+1]=work(i,s[top]);
		top++;
		s[top]=i;
	}
	for(i=1;i<=n;i++)
	{
		printf("%.8lf\n",ans[i]);
	}
	return 0;
}