E. Water Balance(思维+单调栈+平均数)

https://codeforces.com/contest/1300/problem/E

---

思路：如果进行考虑呢？

假设现在有一段区间平均值为x1,有一段区间平均值为x2,现在新加入一个x3。

如果x3<x2,那么必然x3加入是能使平均分降低的，所以把x3加入到x2.那么再看新的x2''是不是小于x1,如果小就加入，不小就继续往后枚举，每次进行判断。

类似单调栈的模拟。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e6+100;
typedef long long LL;
double a[maxn],st[maxn],len[maxn];
LL pos=0;
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL n;cin>>n;
  for(LL i=1;i<=n;i++) {
  	LL x;cin>>x;a[i]=1.0*x;
  }
  for(LL i=1;i<=n;i++)
  {
  	st[++pos]=a[i];
	len[pos]=1;
	while(pos>1&&st[pos]<st[pos-1])
	{
		st[pos-1]=1.0*(st[pos]*len[pos]+st[pos-1]*len[pos-1])/(len[pos]+len[pos-1]);
		len[pos-1]=len[pos-1]+len[pos];
		pos--;	
	}	
  }
  for(LL i=1;i<=pos;i++)
  {
  	for(LL j=1;j<=len[i];j++)
  	{
  		printf("%.12f\n",st[i]);	
	}
  }
return 0;
}
 

 

本文地址：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/108806535