题目描述

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

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

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

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

输入格式
第一行输入整数 $N$ 和 $F$ ，数据间用空格隔开。

接下来 $N$ 行，每行输出一个整数，第$i+1$行输出的整数代表，第i片区域内包含的牛的数目。

输出格式
输出一个整数，表示围起区域内每块地包含的牛的数量的平均值可能的最大值乘以$1000$得到的数值。

数据范围
$1≤N≤100000$
$1≤F≤N$

样例

输入样例：
10 6
6 
4
2
10
3
8
5
9
4
1
输出样例：
6500

前缀和+二分

解题思路：首先我们可以这样理解，我们要寻找一段数列，这个数列满足，长度不小于$L$，并且它的子段和非负。也就是我们需要的二分判定。

二分：首先我们的$mid=(l+r)/2$，记住这里不要是>>1，因为这是浮点数除法。然后呢，我们可以进行前缀和运算,$s[i]=s[i-1]+a[i]-mid$，因为首先我们找的mid是这个平均值，其次前缀和，是为了处理子段和，比如说我要算出$[3,5]$的子段和，那么我们只需要输出$s[5]-s[2]$即可。

这里呢，我们要找到这个满足题意的最优解$[l,r]$，那么也就是说$a[l-1]$要尽量地小，然后$a[r]$要尽量地大，所以说我们就需要枚举这个$l$，但是这样的话时间吃不消，那么怎么办呢？我们发现，每一次$r$变大后，$l$的取值范围从$[1,l]$变成了$[1,l+1]$，所以说我们只需要一个变量，存储当前的最小值即可。具体可看代码实现。

C++ 代码

带check版本

#include <bits/stdc++.h>
using namespace std;
#define fir(i,a,b) for (int i=a;i<=b;i++)
#define eps 1e-5
const int N=100100;
int n,f;
double min_val,ans,l,r,mid,a[N],s[N];
int check(double mid)
{
    fir(i,1,n)
        s[i]=a[i]-mid,s[i]+=s[i-1];
    ans=-1e8,min_val=1e8;
    fir(i,f,n)
    {
        min_val=min(min_val,s[i-f]);
        ans=max(ans,s[i]-min_val);
    }
    return ans<=0?0:1;
}
int main()
{
    cin>>n>>f;   
    fir(i,1,n)
        cin>>a[i];
    l=-1e6,r=1e6;
    while(r-l>eps)
    {
        mid=(l+r)/2;
        if (check(mid))
            l=mid;
        else
            r=mid;
    }
    cout<<(long long)(r*1000);
}

#include <bits/stdc++.h>
using namespace std;
#define eps 1e-5
const int N=100100;
int n,i,j,f;
double a[N],s[N],mid,ans,min_val,l,r;
int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>f;
    for (i=1;i<=n;i++)
        cin>>a[i];
    l=-1e6,r=1e6;
    while(r-l>eps)
    {
        mid=(l+r)/2;
        for (i=1;i<=n;i++)
            s[i]=s[i-1]+a[i]-mid;
        min_val=1e10;
        ans=-1e10;
        for (i=f;i<=n;i++)
        {
            min_val=min(min_val,s[i-f]);
            ans=max(ans,s[i]-min_val);
        }
        if (ans>=0)
            l=mid;
        else
            r=mid;
    }
    cout<<(int)(r*1000)<<endl;
}