莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

1. 用二分法检查avg是不是最大值
2. 用s[i]表示a[i]-avg的前缀和
3. 利用双指针，每更新一个k，mins也要跟着更新，判断s[k]是否大于mins

#include<bits/stdc++.h>

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()
{
    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;
    }

    cout<<(int)(r*1000)<<endl;

    return 0;
}