题目描述

农夫约翰的农场由 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

算法1

(暴力枚举) $O(nlog(L)$

n为牛的数量，L为答案区间

思路：

1. 首先我们二分出答案区间。根据二分我们得出一个mid

2. 对mid作判定，如果我们在整个牛区间中能找到一段f的区间满足他们的均值大于mid，说明我们的mid给小了，否则就是给大了。

3. 如何对mid做判定，mid是作为均值传进check函数，我们只需要将整个区间减去mid,然后对区间求一下前缀和，利用双指针判断一下是否有哪个区间能满足前缀和大于0，大于0 即说明当前给出的mid是小了

C++ 代码

#include<iostream>
#include<algorithm>

using namespace std;

const int N=100010;
int cows[N];
double sum[N];
int n,f;


bool check(double avg)
{
    for(int i=1;i<=n;i++) sum[i]=sum[i-1]+cows[i]-avg;

    double minv=2000;
    for(int i=0,j=f;j<=n;j++,i++)
    {
        minv=min(minv,sum[i]);
        if(sum[j]>minv) return true;
    }
    return false;
}

int main()
{
    cin>>n>>f;
    for(int i=1;i<=n;i++)cin>>cows[i];

    double l=0,r=2000;

    while(r-l>1e-6)
    {
        double mid=(l+r)/2.0;

        if(check(mid)) l=mid;
        else r=mid;
    }

    cout<<int(r*1000)<<endl;
    return 0;
}