Best Cow Fences

问题

给定正整数数列A，求一个平均数最大的、长度不小于L的（连续的）子段。

分析

若数列中存在“一段长度不小于 $L$ 且平均数小于等于 $x$ ”的子段时 ，则一定存在“一段长度不小于 $L$ 且平均数小于等于 $y\;(y > x)$ 的子段”，反之也成立。

因此根据问题的单调性可以将问题转化为“二分判定问题”。每次断定二分值 $x$，判断该正整数数列 $A[]$ 中是否存在一段长度不小于 $L$ 且平均数不小于 $x$ 的子段。若存在则增大二分值 $x$，若不存在则减小二分值 $x$。

假设有子段 $A[l…r]$，判定该子段的平均值是否小于 $x$ 则可以判定 $\sum_{i = l}^{r}A[i] \geq (r-l+1)*x$，变换公式可得 $ \sum_{i = l}^{r} \{A[i]-x\} \geq 0$。于是在每次给定 $x$ 进行判定时，我们可以将数列 $A[]$ 中的每一个数都减去 $x$，并求出前缀和 $S[]$。对于每个 $S[i]$ 查找是否存在 $S[j]$ 满足 $S[i] - S[j] \geq 0, \;(0\leq j\leq i-L)$。注意在实数域上进行二分时以及浮点数转整数输出时的注意事项。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const double eps = 1e-6;
int n, f;
double a[N];
double s[N];
bool solve(double x) {
    s[0] = 0;
    for (int i = 1; i <= n; ++i) {
        s[i] = s[i-1] + (a[i] - x);
    }
    double mins = 0;
    for (int i = f; i <= n; ++i) {
        mins = min(mins, s[i-f]);
        if (s[i] >= mins) {
            return true;
        }
    }
    return false;
}

int main(int argc, const char * argv[]) {
    // freopen("input.txt", "r", stdin);
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);
    scanf("%d%d", &n, &f);
    a[0] = 0;
    for (int i = 1; i <= n; ++i) {
        scanf("%lf", &a[i]);
    }
    double lo = 1e-6;
    double hi = 2001;
    while (hi - lo > eps) {
        double mi = lo + (hi - lo)/2;
        if (solve(mi)) {
            lo = mi;
        } else {
            hi = mi;
        }
    }
    int ans = (lo + eps) * 1000;
    printf("%d\n", ans);

    return 0;
}