该题原题为洛谷P1404 平均数。

本题中需要找出一段不小于m的连续区间并使区间平均值最大。

我们不可能去列出所有可能然后一遍遍去算它们的平均值，但是我们可以尝试给出一个值，然后判断这个值是否符合要求。这个值通过二分区间（-1000000<=Ai<=1000000）产生。将每次得到的中点值mid进行验证(check函数)，如果check函数找到一段区间的平均值大于等于mid，就把左边界改为mid，反之把右边界改为mid-1。

//二分法核心代码
int l = -1000000, r = 1000000;//左边界和右边界
ll mid = (l + r + 1) / 2;
while (l < r)// 当l==r时退出循环，此时的l和r值就是我们想得到的平均值
{
	mid = (l + r + 1) / 2;
	if (check(mid))l = mid;
	else r = mid - 1;
}               

洛谷上本题的二分法核心代码至少有三种，每种之间的区别就在于mid的计算和修改边界值。上面介绍的这种写法是最合理的，别的写法虽然也能过，只是因为 数据强度不足/精度问题 顺利卡过罢了。

那如何判断当前值是否符合条件呢？(check函数的写法)

首先将序列中的元素减去我们尝试的平均值，如果有一段长度不小于m的子段和大于等于0，说明该平均值可行。计算子段和，可以使用前缀和算法（预处理时sum[i]=sum[i-1]+a[i]，计算时直接sum[i]-sum[j]就可以算出j+1~i区间内的和）。在本题中是sum[i] = sum[i - 1] + (numbers[i] - mid)接下来，我们只要开循环计算出ans=sum[i]-sumj，当ans大于等于0时，就可以得到一段长度不小于m、平均值大于等于mid的子段。

bool check(int mid)
{
	for (int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + numbers[i]-mid;//计算前缀和
	}
	for (int i = m; i <= n; i++)
	{
		for (int j = i-m; j >= 0; j--)
		{
			if (sum[i] - sum[j] >= 0)return true;// sum[i] - sum[j]是长度不小于m的子段，如果它大于等于0，该子段的平均值大于等于mid
		}
	}
	return false;
}

非常遗憾的是，它TLE了。我们该如何去优化它？

很明显，程序在第二个循环中耗费了太多时间（二重循环，循环次数最多为5e9）。这一步是计算sum[i] - sum[j]。我们可以发现在sum[i] - sum[j]中，sum[i]的值不变，每次变化的是sum[j]的值。所以我们只要记录下sumj的最小值，然后每次只要计算sum[i] – min { sum[j] } (0<=j<=i-m)就可以算出最大连续子段和，如果最大连续子段和大于等于0，就说明至少有一个长度不小于m的子段符合条件，可以直接返回结果。时间复杂度大大下降！

bool check(int mid)
{
	for (int i = 1; i < m; i++)sum[i] = sum[i - 1] + (numbers[i] - mid);
	for (int i = m; i <= n; i++)
	{
		sum[i] = sum[i - 1] + (numbers[i] - mid);
		minn = min(minn, sum[i - m]);//min(sum[n])n=0~i
		if (sum[i] >= minn)return true;//计算sum[i] – min { sum[j] }
	}
	return false;
}