我的算法书 - 寻找段落

题目描述

给定一个长度为 $n$ 的序列 $a_1, a_2, \ldots, a_n$ ，以及两个整数 $S$ 和 $T$ 。求出在所有长度在 $[S,T]$ 之间的连续子序列中，平均值最大的那个子序列的平均值。

解题思路

问题分析

显然可以暴力,你可以先写一个暴力代码

n = 1e5,暗示我们这个题目是 $O(n)$ 或 $O(nlogn)$

显然这里用到了平均数的性质,所有我们需要看看这个性质是什么,需要去算.

二分答案的可行性

可以想到

答案是上下界的.o

现在思考,答案是否具有二分性


---------------- Real_ANS ---------------------
              ^
              |
              |
估算的值est --+

Estimate: 估算

如果估算的值 est 在Real_ANS的左边,则必然存在段区间 $len \in [S,T]$ 使得平均值大于等于 est。

如果我们能在 $O(n)$ 的时间内知道,est 是在 Real_ANS的左侧,还是右侧,那么这个题目就可以是用二分。

数学变换

因为我们不知道 Real_ANS是多少, 那么我们在不知道Real_ANS的值的情况下判断 est 的左侧还是右侧吗?

P(l,r) : ( \text{est} < \frac{sum(l,r) }{ r-l+1} ) \\ \exist l,r \quad P(l,r)

那么关键就在 $P(l,r)$ 这个公式了,如果枚举 $l,r$ ,时间还是 $O(n^2)$ ,那么把公式变形:

$\text{est} < \frac{sum(l,r) }{ r-l+1}$
$est \times (r-l+1) < sum(l,r)$
$sum(l,r) - est \times (r-l+1) > 0$
$(a_l + a_{l+1} + \cdots + a_r) - est \times (r-l+1) > 0$
$(a_l - est) + (a_{l+1} - est) + \cdots + (a_r - est) > 0$

然后创建一个数组 b[i]: $b[i] = a[i] - est$

通过构造这个新数组 $b$ ，我们的问题就从"寻找平均值 $\ge est$ 的段落"转化成了：在数组 $b$ 中，是否存在一个长度在 $[S, T]$ 之间的段落，且该段落的元素和 $\ge 0$

如果存在这样的段落，说明这个 est 是可行的（甚至还可以更大）；如果不存在，说明 est 太大了。为了快速判断是否存在这样的段落，我们需要频繁计算一段区间 $[i, j]$ 的和。这就引出了下一个问题：有什么常用的技巧或辅助数组，可以让我们在 $O(1)$ 的时间内算出任意一段连续区间的和呢？

显然是前缀和

结合前缀和公式，这个条件就变成了：

S[i] - S[j-1] \ge 0

即：

S[i] \ge S[j-1]

可以想到固定i,然后取枚举 $j-1$ , 然后取最小值, 然后看是否大于0

显然j-1的范围是 $[i-S,i-T]$

那么我们可以枚举i,然后取 $[i-T,i-S]$ 的最小值,然后看是否大于0

直觉理解

直觉: 把a数组的每个数值想象成一个柱子,柱子的高度代表 a[i] 的值.

如果所有的柱子都削去 est 后, 还存在区间和 >=0 , 说明 est 在 Real_ANS 的左边

问题变成: 最大区间和, 朴素方法: 枚举

区间和显然使用 : 前缀和

枚举优化: 固定结尾i,求 S[i] - S[j-1] 是否存在 >=0的

是否存在转成找到S[j-1]的最小值

转成求对应区间 [i-T,i-S] 最小值

区间最值问题

问题变成的区间最值问题

显然我们可以用单调队列来维护这个最小值
也可以是用线段树来维护这个最小值
也可以是用ST表来维护这个最小值
也可以是用分块来维护这个最小值
也可以是用树状数组来维护这个最小值

单调队列优化

这里只能用 单调队列 因为时间. $O(n)$

算法步骤

二分答案，设定上下界
对于每个猜测的平均值 $est$ ：
- 构造数组 $b[i] = a[i] - est$
- 计算前缀和数组 $S$
- 使用单调队列维护长度为 $T-S+1$ 的滑动窗口最小值
- 检查是否存在合法区间使得区间和 $\geq 0$
根据检查结果调整二分边界

时间复杂度

二分答案： $O(\log(\text{精度}))$
每次检查： $O(n)$
总体时间复杂度： $O(n \log(\text{精度}))$

这真是一个好问题, 最难的部分就是思维转换, 把问题变成求区间最值问题

代码实现

cpp

copy

        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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116

        /**
 * Author by Rainboy blog: https://rainboylv.com github : https://github.com/rainboylvx
 * date: 2025-12-24 19:40:34
 * * 算法核心：二分答案 (Binary Search on Answer) + 单调队列优化 (Monotonic Queue Optimization)
 * 复杂度：O(N * log(Answer_Range / EPS))
 */
#include <bits/stdc++.h>
#include <iomanip>
#include <ios>
using namespace std;
typedef  long long ll;
typedef  unsigned long long ull;

const int maxn = 2e6+5;
int n,s,t;
int a[maxn];
double b[maxn], sum[maxn]; // b: 减去二分值后的数组, sum: b数组的前缀和

const double EPS = 1e-5; // 精度控制，用于实数二分结束条件

// 构造辅助数组 b 和前缀和 sum
// 核心思想：原式 (sum[i]-sum[j])/(i-j) >= est 
// 变形为：(sum[i]-sum[j]) >= est * (i-j)
// 移项得：(sum[i] - i*est) - (sum[j] - j*est) >= 0
// 这里的 b[k] = a[k] - est 其实就是把每个元素先减去平均值
// 只要找到一段区间和 >= 0，就说明平均值 >= est
void build_arr_b(double est) {
    for(int i = 1; i <= n; ++i) 
    {
        b[i] = a[i] - est;          // 每个元素减去猜测的平均值
        sum[i] = sum[i-1] + b[i];   // 计算新数组的前缀和
    }
}

// 辅助函数：计算区间和 (当前代码未直接使用，保留作为逻辑参考)
double sum_range(int l,int r) { return sum[r] - sum[l-1]; }

void init(){
    std::cin >> n;
    std::cin >> s >> t;
    for(int i = 1; i <= n; ++i) 
    {
        std::cin >> a[i];
    }
}

// 检查是否存在一个长度在 [S, T] 之间的子段，其平均值 >= est
bool check(double est) {

    build_arr_b(est); // 根据当前的猜测值 est 重构前缀和

    // 单调队列 q，存放的是下标 k
    // 队列性质：队列内的 sum[k] 单调递增
    // 队首 q.front() 始终是当前合法范围内 sum 值最小的那个下标
    deque<int> q; 

    // i 代表子段的【结束位置】
    // 子段范围是 [j+1, i]，其中 j 是我们在单调队列里维护的【前驱位置】(即 sum[j] 中的 j)
    // 长度限制：S <= i - j <= T  ==>  i - T <= j <= i - S
    for(int i = s; i <= n; ++i) 
    {
        // 1. 入队操作：尝试将新的候选前驱 (i-s) 加入队列
        // 只有当 i >= s 时，(i-s) 才能构成至少长度为 s 的区间，是一个合法的起点前驱
        int candidate = i - s;
        
        // 维护单调性：如果新来的 sum[candidate] 比队尾更小，
        // 那么队尾那些 sum 值大的元素永远不可能成为“最优解”（减数越小，结果越大），直接踢出
        while( !q.empty() && sum[q.back()] >= sum[candidate] )
            q.pop_back();
        
        q.push_back(candidate);

        // 2. 出队操作：移除“过期”的元素
        // 如果队首的下标 < i-t，说明以该下标为起点的段落长度 > t，超出了最大长度限制
        while( !q.empty() && q.front() < i-t )
            q.pop_front(); 

        // 3. 判定操作
        if( !q.empty() ) {
            // sum[i] - sum[q.front()] 表示以 i 结尾，以 q.front()+1 开始的区间和
            // 如果这个区间和 >= 0，说明平均值 >= est，check 成功
            if( sum[i] - sum[q.front()] >= 0 )
                return true;
        }
    }

    return false; // 遍历完所有可能并未找到，说明 est 偏大
}

// 二分查找答案
double bs_find(double l, double r) {
    while (r - l > EPS) { // 当区间足够小时停止
        double mid = (l + r) / 2;
        if( check(mid) )
            l = mid; // mid 可行，尝试更大的平均值 (答案在右边)
        else
            r = mid; // mid 不可行，答案在左边
    }
    return l;
}

signed main () {
    ios::sync_with_stdio(false); cin.tie(0);
    init();

    // 确定二分范围：题目数据范围 -1e4 到 1e4
    double max_val = 1e4 + 5; 
    double min_val = -1e4 - 5;

    double ans = bs_find(min_val, max_val);

    cout << fixed << setprecision(3) << ans << "\n";

    return 0;
}

目录