题目描述

农夫约翰的农场由 $N$ 块田地组成，每块地里都有一定数量的牛,其数量不会少于1头，也不会超过2000头。

约翰希望用围栏将一部分连续的田地围起来，并使得围起来的区域内每块地包含的牛的数量的平均值达到最大。

围起区域内至少需要包含 $F$ 块地，其中 $F$ 会在输入中给出。

在给定条件下，计算围起区域内每块地包含的牛的数量的平均值可能的最大值是多少。

输入样例

10 6
6 
4
2
10
3
8
5
9
4
1

输出样例

6500

浮点数二分

时间复杂度 $O(nlogn)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m;
double sum[N],q[N];

bool check(double x)//判断是否存在一种方法使平均值大于x
{
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+q[i]-x;//sun即为于x的差值 妙!!
    double minv=0;//任意大于等于0的数皆可
    for(int i=0,j=m;j<=n;i++,j++)
    {
        minv=min(minv,sum[i]);
        if(sum[j]>=minv) return true;
    }
    return false;
}

double s1(double l,double r)
{
    const double eps=1e-6;
    while(r-l>eps)
    {
        double mid=(l+r)/2;
        if(check(mid)) l=mid;
        else r=mid;
    }
    return r;//取左在向下取整中可能发生错误
}


int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>q[i];
    double x=s1(1,2000);
    printf("%d",(int)(x*1000));//强制类型转换int即为向下取整
}