昨天牛客多校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 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注