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

题解：

题意：给$N$个数，找一个平均值最大的，且长度大于等于$F$的子段。

题目问的是让我们找一个最大值，这种最大，最小的问题，无碍于两种做法，一种是单纯的枚举，另一种是二分查找，当然后面还有一些更高级的算法。这道题的数据范围，很明显是二分查找(其实$10^5$枚举也可以，但是这里并不是整数，是可以存在小数的)。

• 二分查找出来一个平均值$avg$来判定，能否成立一个子段大于等于$F$组且大于等于这个平均值$avg$。

int search()
{
    while(r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if(find(mid)) l = mid;
        else r = mid;
    }

    return (int)(r * 1000); 
}

• 可以利用前缀和，$sum[i] = sum[i-1] + num[i] - avg$ ，如果这个前缀和中存在连续长度大于等于$F$且和大于等于$0$，就成立了。

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

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

    return false;
}

• 关于这个式子怎么推出，😂，我还小，我表达不清楚，如果非要说说，呢，大概是经验告诉我这个式子要这么写。

上全部代码：

#include<bits/stdc++.h>
using namespace std;

const int MAX = 100010;
int num[MAX],n,f;
double l,r;
double sum[MAX];

void init()
{
    cin >> n >> f;

    for(int i = 1;i <= n;++i)
    {
        cin >> num[i];
        r = max(r,(double)num[i]);
    }
}

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

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

    return false;
}

int search()
{
    while(r - l > 1e-5)
    {
        double mid = (l + r) / 2;
        if(find(mid)) l = mid;
        else r = mid;
    }

    return (int)(r * 1000); 
}

int main(int argc, char const *argv[])
{
    ios::sync_with_stdio(false);

    init();

    cout << search();

    return 0;
}