题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

#include <stdio.h>
#include <algorithm>
#include <iostream>
using namespace std;

const int maxn=1e5+5;

int n,m;
double sum[maxn];
int cow[maxn];

bool check(double avg){
    for(int i=1;i<=n;i++){
        sum[i]=sum[i-1]+cow[i]-avg;
    }
    double mins=0;
    for(int i=m,j=0;i<=n;i++,j++){
        mins=min(mins,sum[j]);
        if(sum[i]-mins>=0)return true;
    }
    return false;
}

int main(){
    double l=0,r=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d",&cow[i]);
        r=max(r,(double)cow[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));
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla