最大均值

解题思路

二分答案
可以将序列中的每个数减去二分的值
题目就变为
是否存在一个长度不小于L,平均值不小于mid的子段

AC代码

#include<cstdio>
#include<algorithm>
using namespace std;
int n,L;
double l=-1000000,r=1000000,a[100005],b[100005],sum[100005];
bool check(double x)//判断
{
   
	for(int i=1;i<=n;i++)b[i]=a[i]-x,sum[i]=sum[i-1]+b[i];
	double ans=-2147483647,mmin=2147483647;
	for(int i=L;i<=n;i++)
	{
   
		mmin=min(mmin,sum[i-L]);
		ans=max(ans,sum[i]-mmin);
	}
	return ans>=0;
}
int main()
{
   
	scanf("%d%d",&n,&L);
	for(int i=1;i<=n;i++)
	 scanf("%lf",&a[i]);
	while(l+1e-5<r)//二分
	{
   
		double mid=(l+r)/2;
		if(check(mid))l=mid;else r=mid;
	}
	printf("%d",int(r*1000));
	return 0;
}

谢谢