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
上一篇: 线程同步下的死锁机制
下一篇: 线程同步与互斥(死锁的避免)