前缀和背景下的二分答案 ：平均数

平均数

题目描述

给一个长度为 $n$ 的数列，我们需要找出该数列的一个子串，使得子串平均数最大化，并且子串长度 $\ge m$。

输入格式

第一行两个整数 $n$ 和 $m$。

接下来 $n$ 行，每行一个整数 $a_i$，表示序列第 $i$ 个数字。

输出格式

一个整数，表示最大平均数的 $1000$ 倍，如果末尾有小数，直接舍去，不要用四舍五入求整。

样例 #1

样例输入 #1

10 6
6
4
2
10
3
8
5
9
4
1

样例输出 #1

6500

提示

数据规模与约定

• 对于 $60\%$ 的数据，保证 $m\le n\le 10^4$；
• 对于 $100\%$ 的数据，保证 $1 \leq m\le n\le 10^5$，$0\le a_i\le2000$。

思路：1.先找一个基准数字x；这个基准数的找寻可以使用二分。

2.求出数组中每个数字相对于这个基准数字的偏移量数组。

例如：4 -1 -2 8 -1 的数组，假设我某一轮二分答案的mid为4；

则我找到的偏移量数组为：0 -5 -6 4 -5；

3.接下来，求这个偏移量数组的前缀和数组，便于后续的求和处理；

例如：上述数组的前缀和数组为：0 -5 -11 -7 -12

4. i 从第m位开始遍历到n（数组最后），开始求以 i 为结尾的子串的最大字串和。最大子段和可以转化为前缀和相减的形式。 设sum[i]为序列A的前i项的和 。设s[i]是序列A以A[i]结尾且长度不小于F的最大连续子段和, 那么显然有: s[i] = sum[i] - min{sum[j]}(0<=j<=i-L)

使用minn这个变量记录1~m位置的最小值（因为我们总希望前缀和a[ i ]减去一个尽量小的数字）。但这个过程可以不用再添加一个循环，因为我只需要在一开始，i-m还是0的时候就记录从0号位置，后续随着i 往后移动，每增加一个位置就也相当于放开了i-m号位置，这时判断i-m号位置的元素是不是比前面0_{i-m-1这个号码范围内的元素的最小值更小即可求出0}i-m范围内的最小值。

附上代码：

#include <cstdio>
#define INF 2147483647
#include <iostream>
using namespace std;
const long long MAXN = 100010;
double a[MAXN], sum[MAXN];
long long n, m;
int check(double x)
{
    double presum_of_dis[MAXN] = {0};
    for (long long i = 1; i  <= n; i++)//构造前缀和数组
    {//presum_of_dis为距离基准值x的距离数组的前缀和
        presum_of_dis[i] = presum_of_dis[i - 1]+(a[i]-x);
    }
    double minn=INF,maxn=-INF;
    for(long long i=m;i<=n;i++)
    {
        if(minn>presum_of_dis[i-m])minn=presum_of_dis[i-m];
        if(presum_of_dis[i]-minn>maxn)maxn=presum_of_dis[i]-minn;
    }
     if(maxn>=0)return 1;
     else return 0;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (long long i = 1; i <= n; ++i)
        scanf("%lf", &a[i]);
    double i= 0, j = 2000,ans;
    while (i-j <=0.0000000000001 )
    {
        double mid = (i + j) /2;
        if (check(mid))
        {
            ans=mid;
            i = mid +0.0000001;
        }
        else j = mid -0.0000001;
    }
    cout<<(int)(i*1000)<<endl;
    return 0;
}