形式化题目

给定一个长度为 $N$ 的正整数序列 $A = [a_1, a_2, \dots, a_N]$ 和一个整数 $F$。

求一个长度不小于 $F$ 的连续子段 $A[l \dots r]$（即 $1 \leqslant l \leqslant r \leqslant N$ 且 $r - l + 1 \geqslant F$），使得子段中元素的平均值：

达到最大。最终输出该最大平均值乘以 $1000$ 后的向下取整结果 $\lfloor \text{ans} \times 1000 \rfloor$。

正解

思路

直接枚举所有长度 $\geqslant F$ 的连续子段并计算平均值需要 $O(N^2)$ 的时间复杂度，在 $N = 100000$ 时会超时。

注意到“平均值能否达到 $v$”具有单调性：若存在子段的平均值 $\geqslant v$，则对于任意 $v' < v$，该子段的平均值显然也 $\geqslant v'$。因此可以通过二分答案将最优化问题转化为判定性问题。

1. 判定条件的转化

对于给定的实数 $mid$，判断是否存在区间 $[l, r]$ 满足：

• $r - l + 1 \geqslant F$
• $\frac{\sum_{i=l}^r a_i}{r - l + 1} \geqslant mid$

将不等式变形：

令 $b_i = a_i - mid$，记前缀和 $S_k = \sum_{i=1}^k b_i$（定义 $S_0 = 0$）。则区间 $[l, r]$ 的和为 $S_r - S_{l-1}$。问题等价于：

是否存在 $r$ 和 $l$ 满足 $r - l + 1 \geqslant F$（即 $l-1 \leqslant r - F$），使得：

2. $O(N)$ 线性扫描判定

固定右端点 $r$（$F \leqslant r \leqslant N$），合法左端点前缀下标 $p = l - 1$ 的取值范围是 $0 \leqslant p \leqslant r - F$。

为了使 $S_r - S_p$ 尽可能大，应使减数 $S_p$ 尽可能小。令：

当 $r$ 从 $F$ 增加到 $N$ 时，新加入候选集合的下标仅有 $p = r - F$。我们可以维护一个动态变量 $\min\_S$：在每个 $r$ 处，先用 $S_{r-F}$ 更新 $\min\_S = \min(\min\_S, S_{r-F})$，再检查是否 $S_r \geqslant \min\_S$。若满足则判定成功。

这样，单次判定只需 $O(N)$ 时间。

3. 算法可视化

以样例 $A = [6, 4, 2, 10, 3, 8, 5, 9, 4, 1]$，$F = 6$ 为例，扫描过程中维护窗口左侧前缀最小值：

flowchart LR
    subgraph Scan[右端点扫描 r 从 F 到 N]
        direction TB
        subgraph Candidate[合法起点前缀和池]
            direction LR
            P0["S[0]"] --- P1["S[1]"] --- Pk["..."] --- Pf["S[r-F]"]
        end
        Update["min_l = min(min_l, S[r-F])"]
        Check{"S[r] >= min_l ?"}
        Candidate --> Update --> Check
    end

在二分范围 $[1, 2000]$ 内，以精度 $\text{eps} = 10^{-5}$ 终止二分，总时间复杂度为 $O(N \log \frac{\max A}{\text{eps}})$，可以在时限内通过全部测试点。

代码

Python 版：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-03-31 09:00
# update_at: 2026-03-31 09:00

import sys


def has_valid_fence(prefix_sums: list[float], f: int) -> bool:
    """检查是否存在长度至少为 f 且总和非负的连续子数组。

    维护扫到当前位置右端点 r 时，所有合法左端点 l (0 <= l <= r - f) 对应的
    最小前缀和 min_l。若 prefix_sums[r] - min_l >= 0，说明存在满足条件的区间。
    """
    min_l = 0.0
    for r in range(f, len(prefix_sums)):
        l = r - f
        if prefix_sums[l] < min_l:
            min_l = prefix_sums[l]
        if prefix_sums[r] >= min_l:
            return True
    return False


def check(a: list[int], f: int, mid: float) -> bool:
    """判断平均值能否达到 mid。"""
    prefix_sums = [0.0]
    total = 0.0
    for x in a:
        total += x - mid
        prefix_sums.append(total)
    return has_valid_fence(prefix_sums, f)


def max_average_fence(a: list[int], f: int) -> int:
    """二分平均值求长度至少为 f 的最大连续平均值，结果乘 1000 向下取整。"""
    left = 0.0
    right = 2000.0

    while right - left > 1e-5:
        mid = (left + right) / 2.0
        if check(a, f, mid):
            left = mid
        else:
            right = mid

    return int(right * 1000)


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    try:
        first = next(data)
    except StopIteration:
        return
    n = int(first)
    f = int(next(data))
    a = [int(next(data)) for _ in range(n)]

    ans = max_average_fence(a, f)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 13:54
 * update_at: 2026-10-06 13:54
 */
#include <iostream>
using namespace std;

const int MAXN = 100005;

typedef long long ll;

ll n, f;
ll a[MAXN];        // a[i] 表示第 i 块地里的牛的数量
double sum[MAXN];  // sum[i] 表示前 i 项的 (a[i] - mid) 前缀和，随二分基准 mid 变化

// 判断平均值能否达到 mid，即是否存在长度不小于 f 且总和非负的连续子段。
bool check(double mid) {
    sum[0] = 0.0;
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i] - mid;
    }

    // 固定右端点 r，合法左端点前缀下标 p = l - 1 满足 0 <= p <= r - f。
    // min_sum 维护这些 p 中 sum[p] 的最小值，若 sum[r] >= min_sum 则说明存在合法子段。
    double min_sum = 0.0;
    for (int r = f; r <= n; r++) {
        int p = r - f;
        if (sum[p] < min_sum) {
            min_sum = sum[p];
        }
        if (sum[r] >= min_sum) {
            return true;
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> f;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // 二分最大平均值：平均值可达 mid 具有单调性，左侧可行则抬高下界。
    double left = 0.0;
    double right = 2000.0;
    while (right - left > 1e-5) {
        double mid = (left + right) / 2.0;
        if (check(mid)) {
            left = mid;
        } else {
            right = mid;
        }
    }

    // right 始终略大于真实最大值，乘 1000 后向下取整即为答案。
    ll ans = (ll)(right * 1000);
    cout << ans << "\n";

    return 0;
}

复杂度

• 时间复杂度：单次判定遍历序列一次，耗时 $O(N)$。二分区间长度为 $2000$，精度阈值为 $10^{-5}$，二分迭代次数约为 $\log_2(2000 / 10^{-5}) \approx 28$ 次。总时间复杂度为 $O(N \log \frac{V}{\text{eps}})$，其中 $V = \max a_i$。在 $N = 10^5$ 时，总操作量约 $3 \times 10^6$，耗时远低于 1 秒。
• 空间复杂度：存储输入数组和前缀和数组需要 $O(N)$ 额外空间。

总结

解决“最大平均值连续子段”问题的核心是将平均值减去基准量 $mid$，转化为和非负问题。通过前缀和配合单调更新前缀最小值，消除了固定长度下限带来的多余枚举，将判定复杂度压至 $O(N)$。这种“二分答案 + 偏移量前缀和 + 前缀极值”是处理实数域最值和平均值区间的经典范式。