「一本通 1.2 例 2」Best Cow Fences

形式化题目

给定长度为 $n$ 的正整数序列 $A$ 与整数 $L$ ，在所有长度不小于 $L$ 的连续子段中求最大平均数，输出其 $1000$ 倍（直接截断）。

样例验证连续性：2 10 3 8 5 9 的平均数为 $37/6 \approx 6.17$ ，而 10 3 8 5 9 4 的平均数恰为 $39/6 = 6.5$ ，对应输出 $6500$ 。

正解

思路

朴素做法枚举所有 $O(n^2)$ 个子段再求平均， $n \leqslant 100000$ 时不可行。瓶颈在于"直接求最大平均数"。

第一步：二分答案。 注意到单调性：如果存在长度不小于 $L$ 、平均数不小于 $x$ 的子段，那么对任何 $x' < x$ 同样存在。于是"最大平均数"可以二分——问题转化为判定：

是否存在长度 $\geqslant L$ 的子段，其平均数不小于 $x$ ？

第二步：减法判定。 子段 $[j+1, i]$ 的平均数不小于 $x$ ，等价于

\sum_{k=j+1}^{i}(A_k - x) \geqslant 0.

令 $b_k = A_k - x$ ，记其前缀和为 $\text{prefix}$ ，判定条件变成：存在 $i - j \geqslant L$ 使 $\text{prefix}[i] \geqslant \text{prefix}[j]$ 。

第三步：滑动最小值。 固定右端 $i$ 时， $j$ 只需在 $[0, i-L]$ 中取 $\text{prefix}[j]$ 的最小值。 $i$ 从左到右扫描时窗口右端 $i-L$ 单调右移，用变量 best 维护历史最小即可，单次判定 $O(n)$ ，无需单调队列。

整数化。 先把所有数放大 $1000$ 倍，二分的判定值 $x$ 也是整数，全程避免浮点误差；题面"不用四舍五入"正好对应二分得到的最大可行整数（即下取整）。

下表演示样例在 $x = 6500$ （放大后）时的判定过程， $b_k = 1000A_k - x$ ：

右端 $i$	窗口 $[0, i-6]$ 内最小 $\text{prefix}$	$\text{prefix}[i]$	可行？
6	$\text{prefix}[0]=0$	$b_1+\dots+b_6=-500$	否
7	$\min(0, -500)=-500$	$-1500$	否
8	$\min(0,-500,-1500)=-1500$	$-3500$	否
9	$-3500$	$-2500$	否
10	$-3500$	$\text{prefix}[3] + (10{+}3{+}8{+}5{+}9{+}4)\times1000 - 6\times6500$ ，即 $-3500+0=-3500$	是（取 $j=3$ ，子段 `10 3 8 5 9 4`，差为 $0$ ）

表中 $i=10$ 行： $\text{prefix}[10]-\text{prefix}[3] = (10+3+8+5+9+4)\times1000 - 6\times6500 = 39000-39000 = 0 \geqslant 0$ ，判定可行，故 $6500$ 是答案。

代码

Python 版：

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#!/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-07-05 22:10
# update_at: 2026-07-05 22:10

import sys
from itertools import accumulate


def feasible(scaled: list[int], x: int, L: int) -> bool:
    """判断是否存在长度 ≥ L 的子段，其平均值 ×1000 ≥ x。

    等价于：存在 i ≥ j + L 使 sum(scaled[j+1..i]) - x*(i-j) ≥ 0。
    令 b[k] = scaled[k] - x，只要 i-L 前缀位置的最小 b 前缀和 ≤ 当前前缀和。
    """
    prefix = list(accumulate((v - x for v in scaled), initial=0))  # b 的前缀和
    best = 0                       # 前 i-L 个前缀和的最小值（下标 0..i-L）
    for i in range(L, len(scaled) + 1):
        if prefix[i - L] < best:
            best = prefix[i - L]   # 滑动更新可用起点的最小前缀和
        if prefix[i] - best >= 0:  # 找到一个平均值不小于 x 的子段
            return True
    return False


def solve() -> None:
    data = map(int, sys.stdin.buffer.read().split())
    n, L = next(data), next(data)
    scaled = [next(data) * 1000 for _ in range(n)]  # 先放大 1000 倍，二分全程用整数

    # 二分最大的 x，使存在长度 ≥ L 的子段平均值 ×1000 ≥ x；答案就是最大 x。
    lo, hi = 0, max(scaled)
    while lo < hi:
        mid = (lo + hi + 1) // 2
        if feasible(scaled, mid, L):
            lo = mid
        else:
            hi = mid - 1
    print(lo)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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/**
 * 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-05 00:48
 * update_at: 2026-10-05 00:48
 */

#include <cstdio>

typedef long long ll;

const ll MAXN = 100005;

ll n, L;                // 序列长度、子段最短长度
ll a[MAXN];             // a[i]：第 i 个数放大 1000 倍后的值
ll prefix[MAXN];        // prefix[i]：b[1..i] 的前缀和，其中 b[k] = a[k] - x

// 判断：是否存在长度 >= L 的子段，其平均数 * 1000 >= x。
// 子段 [j+1, i] 平均数 >= x 等价于 sum(b[j+1..i]) >= 0，
// 即 prefix[i] >= prefix[j]；只需 prefix[i] 不小于 j in [0, i-L] 的最小前缀和。
bool check(ll x) {
    prefix[0] = 0;
    for (ll i = 1; i <= n; ++i)
        prefix[i] = prefix[i - 1] + a[i] - x; // 现场累加 b 的前缀和

    ll best = 0; // 窗口 [0, i-L] 内 prefix[j] 的最小值，随 i 右移单调维护
    for (ll i = L; i <= n; ++i) {
        if (prefix[i - L] < best)
            best = prefix[i - L]; // 新进入窗口的位置
        if (prefix[i] >= best)    // 找到平均数不小于 x 的子段
            return true;
    }
    return false;
}

int main() {
    scanf("%lld %lld", &n, &L);
    for (ll i = 1; i <= n; ++i) {
        scanf("%lld", &a[i]);
        a[i] *= 1000; // 整体放大 1000 倍，二分全程用整数，避免浮点误差
    }

    // 二分最大的 x：使存在长度 >= L 的子段平均数 * 1000 >= x
    ll lo = 0, hi = (ll)1e9; // 值域上界：每个数 <= 1e6，放大 1000 倍后 <= 1e9
    while (lo < hi) {
        ll mid = (lo + hi + 1) / 2; // 偏向中点，保证 lo 能推进
        if (check(mid))
            lo = mid;
        else
            hi = mid - 1;
    }
    printf("%lld\n", lo); // 最大可行 x 即答案的 1000 倍（下取整）
    return 0;
}

复杂度

时间：每次判定 $O(n)$ ，二分 $O(\log(1000 \cdot \max A))$ 轮，总计 $O(n \log V)$ ， $n = 10^5$ 时约 $3\times 10^6$ 次基本运算。
空间： $O(n)$ （前缀和数组）。

总结

本题是"二分答案 + 减法判定"的经典模型：把"最大化平均值"变成"平均值不小于 $x$ 是否可行"，再把每个数减去 $x$ 后用前缀和与滑动最小值完成判定。凡是"存在一段长度不小于 $L$ 的子段满足平均值条件"的问题，都可以套用这套转化。

「一本通 1.2 例 2」Best Cow Fences

目录

形式化题目

正解

思路

代码

复杂度

总结