题面
题目求平均数最大的子段, 有长度下限m.
转化为答案判定, 就是对于给定的平均数aver, 能否找到一个长度不小于m的满足平均数不小于aver的子段.
把整个数组减去aver, 就变成了判断有没有和为非负的子段. 若有非负子段, 则aver还可以往大猜;否则aver要变小.
所以问题最终转化为了求最大连续子段和, 而连续字段和可以化为前缀和相减的形式.
因此所求即为:
$$\max_{m<=i<=n}\{S_i-\min_{1<=j<=i-m}\{S_j\}\}$$
注意到i每变化1时j上界增加一, 下界不变, 只要用一个变量不断更新$latex S_j$的最大值即可.
特别注意: 实数域上的二分, 要求保留k位小数, eps一般取1e-(k+2), 精度太高也会WA.也可以采用固定次数循环的二分方法.
#include<cstdio>
#include<cstring>
#include<cmath>
#define in inline
#define re register
#define int long long
#define db double
in int read()
{
int s(0),b(0);char ch;
do{ch=getchar();if(ch=='-')b=1;}while(ch<'0'||ch>'9');
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
if(b) return -s;
return s;
}
int n,len;
db a[100010],b[100010],s[100010];
in bool chk(db aver)
{
for(re int i=1;i<=n;++i) b[i]=a[i]-aver;
for(re int i=1;i<=n;++i) s[i]=s[i-1]+b[i];
db ans=-1e6,mins=1e6;
for(re int i=len;i<=n;++i)
{
mins=mins<s[i-len]?mins:s[i-len];
ans=ans>s[i]-mins?ans:s[i]-mins;
}
if(ans>=0) return true;
return false;
}
signed main()
{
n=read(),len=read();
for(re int i=1;i<=n;++i) scanf("%lf",&a[i]);
db l=0,r=1e6,mid;
while(fabs(l-r)>1e-8)
{
mid=(l+r)/2.0;
if(chk(mid)) l=mid;
else r=mid;
}
printf("%lld\n",(int)(r*1000.0));
return 0;
}
CGaZn的博客
最新评论