POJ P2018 Best Cow Fences

目录：

---

题目：

传送门

---

分析：

我们可以用二分求平均值，然后将输入的数列减去平均值，随后利用前缀和，求出在当前平均数下的最大值。
对于二分的左右边界，我们可以通过对求出的最大值进行判断。

---

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#define LL long long
using namespace std;
inline LL read() {
    LL d=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){d=d*10+s-'0';s=getchar();}
    return d*f;
}
double minn,maxn,a[100001],sum[100001],b[100001];
int main()
{
    int n=read(),m=read();
    for(int i=1;i<=n;i++)
      scanf("%lf",&a[i]);
    double eps=1e-5;//精确度
    double l=-1e6,r=1e6;
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        for(int i=1;i<=n;i++) b[i]=a[i]-mid;
        for(int i=1;i<=n;i++)
          sum[i]=sum[i-1]+b[i];
        minn=1e10;maxn=-1e10;
        for(int i=m;i<=n;i++)
          {
            minn=min(minn,sum[i-m]);
            maxn=max(maxn,sum[i]-minn);
          }
        if(maxn>=0) l=mid;
        else r=mid;
    }
    printf("%d",int(r*1000));
    return 0;
}