洛谷-P1419 寻找段落 题解

题目链接：https://www.luogu.com.cn/problem/P1419

题目大意

给定一个长度为 n 的整数序列 a，以及两个整数 S 和 T。要求在所有长度在区间 [S, T] 内的连续子数组中，找出平均值最大的那个，并输出其平均值（保留三位小数）。

解题思路

1. 暴力法不可行

若直接枚举所有满足长度在 [S, T] 范围内的子数组，时间复杂度为：O(n * (T - S + 1))约等于 O(n^2)对于 n = 10^5 来说显然会超时。

2. 二分答案 + 单调队列优化

我们考虑使用 二分答案 的思想：

我们可以构造新数组 bi = i - mid，然后判断是否存在长度在 [S, T] 的子数组，其和 >=0。

这一步可以通过前缀和 + 单调队列高效完成。

3. 判断函数 check(mid)

• 构造数组 bi = ai - mid
• 计算前缀和数组 sum[i]
• 对于每个右端点 i，我们要找左端点 j，使得：i - j 属于[S, T]，即 j 属于 [i - T, i - S]并且 sum[i] - sum[j] >= 0，即 sum[j]<=sum[i]

所以，我们需要在滑动窗口 [i - T, i - S] 中维护最小的 sum[j]。这可以用单调递增队列实现。

4. 二分范围

由于 ai 属于 [-10^4, 10^4]$，所以平均值也在该范围内。我们可以在 [-10000, 10000] 范围内进行二分，精度控制到 1e-5 即可满足三位小数的要求。

算法步骤总结

1. 读入数据。
2. 设定二分上下界 l = -10000, r = 10000。
3. 二分答案：计算 mid = (l + r)/2调用 check(mid) 判断是否存在合法子数组平均值>= mid若存在，则说明答案至少为 mid，令 l = mid否则，令 r = mid
4. 输出最终答案，保留三位小数。

时间复杂度分析

• 二分次数：约 35 次
• 每次 check：O(n)
• 总体复杂度：O(n*log （max_val)/ϵ），完全可以通过 n = 10^5 的数据。

代码解析（关键部分）

bool check(double x) {
    // 构造 b[i] = a[i] - x
    for (i = 1; i <= n; i++)
        a[i] = (double)b[i] - x;

    // 前缀和
    sum[0] = 0;
    for (i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i];

    int l = 1, r = 0; // 单调队列头尾
    for (i = 1; i <= n; i++) {
        // 当前可以加入 i-s 作为候选左端点
        if (i >= s) {
            while (r >= l && sum[i - s] < sum[q[r]]) r--;
            q[++r] = i - s;
        }
        // 移除超出 [i-t, i-s] 范围的队首
        if (l <= r && q[l] < i - t) l++;
        // 判断是否存在 sum[i] - sum[q[l]] >= 0
        if (l <= r && sum[i] - sum[q[l]] >= 0) return true;
    }
    return false;
}

• 单调队列 q 存储的是下标，保证对应的 sum 值单调递增。
• 每次只保留可能成为最小值的候选位置。