C++14(g++5.4) 解法, 执行用时: 48ms, 内存消耗: 2204K, 提交时间: 2020-05-06 22:25:26

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int cow[N],n,m;
double sum[N];
bool check(double mid)
{
	for(int i=1;i<=n;i++)
	sum[i]=sum[i-1]+cow[i]-mid;
	double minv=0;
	for(int i=0,j=m;j<=n;j++,i++)
	{
		minv=min(minv,sum[i]);
		if(sum[j]>=minv)return true;
	}
	return false;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>cow[i];
	double l=0,r=2000;
	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;
}

Python3 解法, 执行用时: 1565ms, 内存消耗: 16144K, 提交时间: 2023-06-27 22:36:00

n,f=map(int,input().split())
cows=[]
pre=[0]
for _ in range(n):
    cows.append(int(input()))
    pre.append(pre[-1]+cows[-1])
def check(mid):
    new=[it*1000-i*mid for i,it in enumerate(pre)]
    max_=-float('inf')
    min_=float('inf')
    for i in range(f,n+1):
        min_=min(min_,new[i-f])
        max_=max(max_,new[i]-min_)
    if max_>=0: return 1
    else: return 0
l=0
r=max(cows)*1000
while l<r:
    mid=(l+r)//2+1
    if check(mid): l=mid 
    else: r=mid-1 
print(r) 
        

C++ 解法, 执行用时: 36ms, 内存消耗: 1528K, 提交时间: 2021-12-18 18:49:58

#include<iostream>
using namespace std;
int N,F,a[100010];
double sum[100010];
bool check(double ave){
	for(int i=1;i<=N;++i)sum[i]=sum[i-1]+a[i]-ave;
	double minpre=0;
	for(int i=0,j=F;j<=N;++i,j++){
		minpre=min(minpre,sum[i]);
		if(sum[j]>=minpre)return 1;
	}
	return 0;
}
int main(){
	cin>>N>>F;
	for(int i=1;i<=N;++i)cin>>a[i];
	double l=0,r=2000,esp=1e-5;
	while(l+esp<r){
		double mid=(r+l)/2;
		if(check(mid))l=mid;
		else r=mid;
	}
	cout<<int(1000*r);
}

C++(g++ 7.5.0) 解法, 执行用时: 57ms, 内存消耗: 1904K, 提交时间: 2023-07-05 10:49:41

#include<bits/stdc++.h>
using namespace std;
double a[100001],b[100001],l=-1e6,r=1e6;
int n,f;
int main(){
	cin>>n>>f;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	while(r-l>1e-5){
		double mid=(l+r)/2,ans=-1e10,mi=1e10;
		for(int i=1;i<=n;i++){
			b[i]=b[i-1]+a[i]-mid;
		}
		for(int i=f;i<=n;i++){
			mi=min(mi,b[i-f]);
			ans=max(ans,b[i]-mi);
		}
		if(ans>=0){
			l=mid;
		}
		else{
			r=mid;
		}
	}
	cout<<int(r*1000);
	return 0;
}