【题解】最大平均数(二分区间求最大子段和)
本文最后更新于 46 天前,其中的信息可能已经有所发展或是发生改变。

该题原题为洛谷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;
}
文章标题:【题解】最大平均数(二分区间求最大子段和)
文章链接:https://intmain0.com/184/
本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处
评论和私信会在第一时间回复。如果您觉得文章对您有帮助,可以点击文章右下角【分享】一下。您的鼓励是博主的最大动力!
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇