区间最大平均值

最大平均值

---

涉及知识点

前缀和，二分判定等

思路

求最大区间平均值，可以先想求又没有区间平均值大于一个固定值A
即在这个序列里
$a_1\ a_2 \ a_3 \ .... \ a_i \ ... \ a_j \ ..... \ a_n \ ..$a1​ a2​ a3​ .... ai​ ... aj​ ..... an​ ..
有没有一段
$(a_i + ... + a_j ) / L >= A$(ai​+...+aj​)/L>=A


变换公式,问题变成求：
$(a_i - A) + ... + (a_j - A) >= 0$(ai​−A)+...+(aj​−A)>=0


将$a_i - A$ai​−A记作$b_i$bi​
问题变成求是否区间和：
$b_i + .. + b_j>= 0$bi​+..+bj​>=0


变成求：$sum[j] - sum[i - 1] >= 0$sum[j]−sum[i−1]>=0

以$j$j为结尾，在前面找个最小的$sum$sum

本题：
假设如果一个序列的最大区间平均值为$12$12,那么一定能找到区间和为$11、10、9....$11、10、9....的，一定找不到区间平均值为$13、14、15...$13、14、15... 的
所以可以二分判定答案，每次一个mid， 判断合不合法(通过上面数组变换成求区间和大于0)
这个题就是111111111000000000求最后一个1的情况

本题还有一个条件$i, j$i,j距离得大于等于m,这里不说了，看代码实现

#include<iostream>
using namespace std;
#define MAX_N 100005
long long n, m;
long long a[MAX_N], b[MAX_N], sum[MAX_N];
long long l, r;

long long check(long long x) {
    for (long long i = 1; i <= n; i++) {
        b[i] = a[i] - x;
        sum[i] = sum[i - 1] + b[i];
    }
    long long y = 0x3f3f3f3f;
    for (long long i = m; i <= n; i++) {
        y = min(y, sum[i - m]);
        if (sum[i] - y >= 0) return 1; 
    }
    return 0;
}

int main() {
    cin >> n >> m;
    l = 0x3f3f3f3f, r = -0x3f3f3f3f;
    for (long long i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] *= 1000;
        l = min(l, a[i]);
        r = max(r, a[i]);
    }
    while (l != r) {
        long long mid = (l + r + 1) / 2;
        if (check(mid)) l = mid;
        else r = mid - 1;
    }
    cout << l << endl;
    return 0;
}