[POJ2018][洛谷P1404]平均数/Best Cow Fences[二分答案]

#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;
}