难度： 黄/绿

算法： 二分，dp

首先，这题要用浮点数。但是浮点数很容易出现不可预知的错误，比如卡精度。那么考虑转化为整数。由于题目是要乘 $1000$ 后直接输出（直接输出意味着向下取整），考虑在输入时直接对每个数乘 $1000$，从而规避对浮点数的计算。

然后这个题可以直接二分答案。判断合法性方法：如果存在一种选法使得平均数大于等于 $c$，那么将每个数减 $c$ 后存在一种选法使得平均数大于等于 $0$，相当于选出来的这段的和为非负数。那么如果能选出一个长度不小于 $L$ 且和为非负的子段，那么就合法。进一步，如果最大子段和为非负数，那么就合法。否则不合法。

那么现在问题就转化成了在一个序列中找其长度大于等于 $L$ 的最大子段和。记 $s_i$ 为第 $i$ 项前缀和，$dp_i$ 为以 $i$ 结尾长度不小于 $L$ 的子段和，那么有 $dp_i=s_i-min(s_j)(0\le j\le i-L)$。从 $L$ 到 $n$ 一边跑一边维护第二项即可。最大子段和为 $max(dp_i)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a[100100],f[100100],ans,x;
ll le,ri,mid;
int main(){
	scanf("%lld%lld",&n,&m);
	for(ll i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		a[i]*=1000;
	} 
	le=0,ri=2e6;
	while(le<ri){
		mid=(le+ri+1)/2;
		ans=-1,x=0x3f3f3f;
		for(ll i=1;i<=n;i++) f[i]=a[i]-mid;
		for(ll i=1;i<=n;i++) f[i]+=f[i-1];
		for(ll i=m;i<=n;i++){
			x=min(x,f[i-m]);
			ans=max(ans,f[i]-x);
		}
		if(ans<0) ri=mid-1;
		else le=mid;
	}
	printf("%lld",ri);
}