最佳牛围栏(实数域上的二分)

传送门：

思路：

朴素思路：直接枚举田地的数量，用前缀和求不同区间长度下的区间和最大值除长度，然后取个max，但最差的情况下要1~1e5的区间长度都枚举一次，等差数列的时间复杂度，O(n^2),超时了

二分思路：二分平均值的大小，判断“是否存在一个长度不小于f的区间，平均数不小于mid”，这里因为答案是有小数的，有精度问题。将原本的数组减去mid的值之后，如果每个点原本的数小于mid会小于0，大于mid会大于0，算出前缀和数组后就可以知道某一段区间和的平均数与mid的关系了，可以转化为判断“是否存在一个长度不小于f的区间，区间和非负”

注意：最后答案要用r*1000，l*1000可能会有问题。

斜率优化思路：........

代码：

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
typedef pair<int ,int> PII;
const int N=1e5+10;
double a[N];
double sum[N];
int n,f;
int main()
{
    cin>>n>>f;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    double  eps=1e-5;
    double l=-2e3+10;
    double r=2e3+10;
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        for(int i=1;i<=n;i++) sum[i]=a[i]-mid;
        for(int i=1;i<=n;i++)
            sum[i]+=sum[i-1];
    double  ans=-1e9;
    double min_res=1e9;
      for(int i=f;i<=n;i++)
     {
         min_res=min(min_res,sum[i-f]);
         ans=max(ans,sum[i]-min_res);
     }
        if(ans>=0) l=mid;
        else  r=mid;
    }
    cout<<int(r*1000)<<endl;
return 0;
}