POJ 2018 Best Cow Fences 二分答案,前缀和

题意

给定长度为n的序列，求长度为[m,n]的子序列的最大平均值

思路

简单分析发现本题答案存在单调性，可以采用二分答案的思路

序列中每个值对于平均值的贡献度为 ${cows[i]-avg}$

可以到当本序列的 $\sum_{begin}^{len} cows[i]-avg =0$ 时，本平均值avg成立

子序列的长度可以为[m,n-m]的任意数字

我们进行二分时要尽量使 $\sum_{begin}^{len} cows[i]-avg >=0$

可得前缀和公式 $contri[i]=contri[i-1]+cows[i]-avg$

所以序列 $cows_[i,j]$ 的 $\sum_{begin}^{len} cows[i]-avg$ 的值为 $contri[j]-contri[i]$

我们在保持最短长度m的前提下，子序列的前端取贡献度最小的值，也就是令 $contri[i]$ 取可取的最小值

即为当
$ $max_{m<=j<=n}\{contri[j]-min_{0<=i<=j-m}\{contri[i]\}\}>=0$ $
时，当前avg值可行，缩小左区间，否则缩小右区间

注意最后输出卡精度

#include<cstdio>
#include<algorithm>
using namespace std;
#define eps 1e-7
typedef long long ll;
ll n, m;
ll cows[100005];
double contri[100005];
bool check(double x) {
    contri[0] = 0;
    for (ll i = 1; i <= n; i++) {
        contri[i] = contri[i - 1] + cows[i] - x;
    }
    double mi = 0x3f3f3f3f3f;
    ll i = 0;
    for (ll j = m; j <= n; j++) {
        mi = min(mi, contri[i]);
        if (contri[j] - mi >= 0) {
            return true;
        }
        i++;
    }
    return false;
}
int main(void) {
    double left = 0.0, right = 0.0;
    scanf("%lld%lld", &n, &m);
    for (ll i = 1; i <= n; i++) {
        scanf("%lld", cows + i);
        right = max(right, (double)cows[i]);
    }
    double mid;
    while (left + eps < right) {
        mid = (right + left) / 2.0;
        if (check(mid)) {
            left = mid;
        }
        else {
            right = mid;
        }
    }
    printf("%.0lf", (right * 1000));
    return 0;
}