欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

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

程序员文章站 2022-03-10 16:03:26
https://codeforces.com/contest/1300/problem/E思路:如果进行考虑呢?假设现在有一段区间平均值为x1,有一段区间平均值为x2,现在新加入一个x3。如果x3#include#include<...

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

相关标签: 思维 单调栈