loj#10012\poj2018 Best Cow Fences(二分)

题目

#10012 「一本通 1.2 例 2」Best Cow Fences

解析

有序列\(\{a_i\}\)，设\([l,r]\)上的平均值为\(\bar{x}\)，有\(\sum_{i=l}^r(a_i-\bar{x})=0\)
这样我们就可以通过二分平均值，
先同减二分到的平均值，若存在一段区间的和大于等于0，说明这段区间的平均值大于等于二分值，上调边界，否则下调边界
只需要枚举右端点\(r\)，判断\(sum[r]-sum[l-1]>=0(1\leq l\leq r - m + 1)\)即可

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const double EPS = 1e-9;

int n, m;
double a[N], sum[N];

int main() {
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    double l = -1000000.0, r = 1000000.0;
    while (r - l > EPS) {
        double mid = (l + r) / 2;
        for (int i = 1; i <= n; ++i) sum[i] = a[i] - mid + sum[i - 1];
        double ans = -INF, mn = INF;
        for (int i = m; i <= n; ++i)
            mn = min(mn, sum[i - m]), ans = max(ans, sum[i] - mn);
        if (ans >= 0) l = mid;
        else r = mid;
    }
    cout << int(r * 1000);
}