头部背景图片
Decaku 's Blog |
Decaku 's Blog |

codeforces 1300E Water Balance

题意:给你n个数,然后你可以把任意一个连续子段里的所有数替换成它们的均值,
这个操作可以执行任意次,最后询问字典序最小的结果。


$有一个比较明显的东西是结果的字典序最小,那么结果的前缀和数组的字典序 \\
也一定是最小的,定义p数组为a数组的前缀和,那么如果我们对[l,r]做一次操作 \\
设(l<=i<=r),则p[i]=p[l-1]+(p[r]-p[l-1])/(r-l+1)*(i-l+1),然后我们把(i,p[i]) \\
看成二维平面上的一个点,那么这个操作可以看成是在两个点之间连一条线,让中间 \\
所有点都落在这条线上,此时发现字典序最小的结果就是原来这些点组成凸包的下凸壳。\\$


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

const int maxn=1e5+5;
ll a[maxn],sum[maxn],st[maxn],top=0;
int main()
{
IOS
int n;cin>>n;
rep(i,1,n) {cin>>a[i];sum[i]=sum[i-1]+a[i];}
rep(i,1,n)
{
while(top&&(sum[i]-sum[st[top]])*(i-st[top-1])<=(sum[i]-sum[st[top-1]])*(i-st[top])) --top;
st[++top]=i;
}
rep(i,1,top)
{
double ret=(sum[st[i]]-sum[st[i-1]])*1.0/(st[i]-st[i-1]);
rep(j,st[i-1]+1,st[i]) cout<<fixed<<setprecision(10)<<ret<<"\n";
}
}
avatar Decaku 菜菜菜