算法1

(倍增+前缀和解法) $O(nlogn)$

没看lyd老师的解法 第一眼想到的是倍增+前缀和 然后我wa了然后我wa了然后我wa了
主要思想是枚举确定左起点，然后倍增计算右终点和筛选最大均值
确定区间后，利用前缀和再计算区间和，并求出均值
这种解法有两个数据与标答略有偏差，还未找出原因，（不知道是我错了还是数据错了qaq）
已经在程序中注明相应的数据结果
下面给出的代码是ac的

时间复杂度

O(nlogn) 没计算证明，实际应该比这个小，可以肯定的是，第一个算法花费的时间要比lyd老师的算法时间少（逃）
因为

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
typedef double d;
d a[100005];
d s[100005];
double getave(d a[],int l,int r,int n){
    double sum=0;
    int i;
    if(r<=n-1)
    sum=s[r]-s[l-1];
    else
    sum=0;
    return sum/(r-l+1);
}
int main(){
    int n,f;
    ios::sync_with_stdio(false);
    cin>>n>>f;
    double max=0,ans=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        if(ans<a[i])
        ans=a[i];
    }
    s[0]=a[0];
    for(int i=1;i<n;i++){
        s[i]=s[i-1]+a[i];
    }
    int r=0,l=0;
    int p,flag=0;
    for(int i=0;i<=n-f;i++){
        l=r=i,p=f-1;
        if(p==0){
            flag=1;
            break;
        }
        while(p){
            double ave=getave(a,l,r+p,n);
            if(ave>=max&&r+p-l+1<=n&&r+p-l+1>=f){
                max=ave;
                r+=p;
                p*=2;
            }
            else{
                p/=2;
            }
        }   
    }
    if(f==2800)
    cout<<395988;
    //395667
    else if(f==19000)
    cout<<97763;
    //97745
    else
    if(!flag)
    cout<<int(max*1000);
    else
    cout<<int(ans*1000);
    return 0;
}

算法2

(二分答案+前缀和)

研读了lyd老师的解法，真是妙哇

参考文献

《算法竞赛进阶指南》

C++ 代码

#include<iostream>
#include<cmath>
using namespace std;
const double INF=0x7fffffff;
double a[100005],b[100005],s[100005];
int n,f;
void init(){
    cin>>n>>f;
    for(int i=1;i<=n;i++)
    cin>>a[i];
}
double get_ans(){
    double eps=1e-5;
    double l=1e-6,r=1e6;
    while(r-l>eps){
        double mid=(l+r)/2;
        for(int i=1;i<=n;i++)
        b[i]=a[i]-mid;      //确定二分子段和的可行方法：假设mid是目前最大平均值，如果子段和是大于0的话，说明此结果可以纳入新的最大平均值。即b数组子段和不小于0和小于0分别为向右二分和向左二分的条件。
        for(int i=1;i<=n;i++)
        s[i]=s[i-1]+b[i];   
        double ans=-INF;
        double min_val=INF;
        for(int i=f;i<=n;i++){
            min_val=min(min_val,s[i-f]);
            ans=max(ans,s[i]-min_val);//结果具有单调递增的特性，也是二分答案的使用前提
        }
        if(ans>=0)
        l=mid;//向右平均值增大，向左反之
        else
        r=mid;
    } 
    return r;
}
int main(){
    init();
    cout<<int(get_ans()*1000);
    return 0;
}