二分

参考资料：算法提高课

分析（固定右端点）

代码

#include <iostream>

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; // s[0]=0;
    for(int i=F;i<=n;i++)
    {
        mins = min(mins,s[i-F]);
        //if(s[i] - mins >= avg) return true;
        if(s[i] - mins >= 0) return true;
    }
    return false;
}

int main()
{
    cin >> n >> F;

    double l=0,r=0;
    for(int i=1;i<=n;i++) 
    {
        cin >> 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;
}