最佳牛围栏

算法

二分 + 前缀和 + 双指针$O(n)$

算法内容：

• 为什么可以二分avg？
  因为我么要找的是最大的avg，其具有二段性
• 如何写check函数？
  check函数表示有没有一段长度大于等于F的区间，使这段区间的平均数尽可能的大，如果我们找到了这样的的区间且这段区间的平均数大于我们二分的平均数，则返回true，否则返回false
  那么如何找到一段长度大于等于F的区间，使这段区间的平均数尽可能大呢？
  首先我们要知道：对于一段序列，让每个数都减去我们算的平均数后。如果这段序列的和大于0，则说明这段序列的平均值比我们算的平均值大，反之小。我们枚举区间的右端点k,每一个右端点对应的区间为1~k, 2~k, 3_{k,...,(k-F+1)}k。所以问题转化为是否存在一段区间使得max(s[k] - s[l - 1]) >= 0，即s[r] - min(s[l - 1]) >= 0。那么如何找出min(s[l - 1])呢？我们可以用一个变量mins来不断更新

C++代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, F;
double a[N], s[N];

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

    double mins = 0;
    for (int k = F; k <= n; k ++ )
    {
        mins = min(mins, s[k - F]);
        if (s[k] >= mins) return true;
    }

    return false;
}

int main()
{
    scanf("%d%d", &n, &F);

    double l = 0, r = 0;
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%lf", &a[i]);
        r = max(r, a[i]);
    }

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

    printf("%d\n", (int)(r * 1000));

    return 0;
}