---

解题思路

这道题显然需要二分一个平均值，
问题是小数怎么二分呢？
我们可以定义 l , r , m i d l , r , m i d l,r,mid 为 d o u b l e double double类型，
并在判断时加上一个 e p s eps eps即可。（ e p s eps eps是在函数程序中事先声明的常量，是控制迭代精度的，相当于微积分里面的无限小值）

这个问题解决了，我们发现还有一个问题：
判断当前二分到的平均值是否满足条件是 O ( n 2 ) O(n^2) O(n2)，会超时。
首先想到前缀和优化。
此时判断区间为 m a x ( s u m i − s u m i − j + 1 ) max(sum_i-sum_{i-j+1}) max(sumi​−sumi−j+1​) ( l < i ≤ n , j ≤ i − l ) (l<i≤n,j≤i−l) (l<i≤n,j≤i−l)
不难发现 j 只会在 1 1 1~ i − l i − l i−l 中循环比较，直接 max ⁡ 即可，可以省掉一个for循环。
然后注意让当前区间的 s u m i − j + 1 sum_{i-j+1} sumi−j+1​最小即可得到较优答案。

---

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

const double eps=1e-5;
int n,k;
double l,r,mid,sum[200000],a[200000];

bool check(double lyx)
{
	for(int i=1;i<=n;i++)
		sum[i]=sum[i-1]+a[i]-lyx;
	double mann=2147483600,ans=-2147483600;
	for(int i=k;i<=n;i++)
	{
		mann=min(mann,sum[i-k]);
		ans=max(ans,sum[i]-mann);
	}
	if(ans>=0)return 1;
	else return 0;
}

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++)
		scanf("%lf",&a[i]);
	l=-1e6,r=1e6;
	while(l+eps<r)
	{
		mid=(l+r)/2;
		if(check(mid))
			l=mid;
		else r=mid;
	}
	cout<<int(r*1000);
}