昨天牛客多校4上的一道签到题居然没搞出来。。。实在是非常愧疚。最终要点在于O(n*logn)求出一个数组的最大子段平均数。
模板题是luogu的P1404,下文根据本题来进行讲述。
给一个长度为 n 的数列,我们需要找出该数列的一个子串(即连续),使得子串平均数最大化,并且子串长度 \ge m。
其中1\le n\le m \le 10^5 并且 a_i \le 2*10^3
对于这样一个基于10^5范围的复杂度,我们可以想到二分答案。我们可以尝试给出一个值,然后判断这个值是否符合要求。这个值通过二分产生。
//本人更习惯使用的二分模板(整数)
int l=0,r=MAX,mid,ans;
while(l<=r){
mid=(l+r)/2;
if(check(mid)){
ans=mid;
l=mid+1;
}
else r=mid-1;
}
确定了使用二分之后要在O(n)的限制下写出一个check()函数
首先将序列中的元素减去我们尝试的平均值,如果有一段长度不小于m的子段和大于等于0(即存在子段和大于等于该平均值),说明该平均值可行。
计算子段和,可以使用前缀和(预处理时sum[i]=sum[i-1]+a[i],计算时直接sum[i]-sum[j]就可以算出[j+1,i]内的和)。在本题中是sum[i] = sum[i – 1] + (a[i] – mid)接下来,我们只要开循环计算出ans=sum[i]-sum[j],当ans \ge 0时,就可以得到一段长度不小于m、平均值大于等于mid的子段。
bool check(int mid){
for (int i=1;i<=n;i++){
sum[i]=sum[i-1]+a[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;
}
很明显上述写法是O(n^2)的,不能满足我们的要求。因此我们想办法压到一层循环进行解决。
不难发现第二层循环是计算sum[i] – sum[j]。我们可以发现在sum[i] – sum[j]中,sum[i]的值不变,每次变化的是sum[j]的值。所以我们只要记录下sum[j]的最小值,然后每次只要计算sum[i] – sum[j]_{min} (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] + (a[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;
}
本文部分转载于【题解】最大平均数 (文转侵删)
0 条评论