企业官网建设流程全解析

前阵子刷题的时候又看到这道题：编号P2884，名字叫《假期》。题面本身并不复杂，但它是“平均值最值 + 长度限制”这类问题的绝佳入门代表，能把二分答案、前缀和、单调队列三个基础工具串成一条线。很多人第一次做的时候会卡在两个地方：一是想不明白“好好的求最大值，为什么要转成判断某个值行不行”；二是搞不清单调队列里到底存的是什么、维护的是什么。这篇文章就把整条思路从头拆一遍，代码也给到可以直接抄作业的程度。

1. 先拆题意：这是一个带长度上下限的“最大平均段”问题

1.1 题目到底在说什么

题面大意是这样的：牧场里记录了连续 N 天的每日产奶量，可能是正数也可能是负数。要给奶牛安排一段连续的“假期”，假期的天数不能太短，至少 L 天；也不能太长，最多 R 天。在满足这个长度限制的前提下，要让假期里“平均每天的产奶量”最大，输出这个最大平均值。

用数学一点的话说：给定数组 a[1..N]，找一个区间 [l, r]，使区间长度满足 L ≤ r - l + 1 ≤ R，目标是最大化：

avg(l, r) = (a[l] + a[l+1] + ... + a[r]) / (r - l + 1)

N 的范围可以去到 10^5 级别，L 和 R 是正常范围的正整数，产奶量可以是负的。看到这个数据范围，基本就宣告了 O(N^2) 思路的死刑，同时也暗示了正解大概率是“二分答案 + 某个 O(N) 的判定过程”。

1.2 为什么不能直接无脑滑动窗口

有人第一反应是：长度在 [L, R] 之间，那就枚举长度 K，从 L 到 R 各跑一遍固定长度的滑动窗口，取最大值，总复杂度 O((R-L+1) * N)。这个思路在 R - L 很小的时候没问题，可一旦长度区间拉大，比如 L=1、R=N，这个做法瞬间退化成 O(N^2)，跑不动。

还有一个更微妙的点：就算只求“长度恰好为 K”的最大平均值，滑动窗口直接做很轻松，因为窗口大小固定，只需要维护窗口总和。可现在长度是一个范围，平均数是一个除法，分母在变。窗口里多加一天，平均值的变化不仅取决于新加的值，还取决于当前窗口长度，这导致我们没法用一个简单的“继承上一窗口最大值”的递推来解决问题。

1.3 平均值的“非线性”才是麻烦根源

为什么“最大子段和”有经典的 O(N) 贪心动态规划，而“最大平均值子段”这么难受？因为子段和是线性的：延续一段会直接加上新的数，我们可以用“要不要从新起点开始”来判断。但平均值等于总和除以长度，这个长度每时每刻都在变化。你可能找到一段“局部精华”，但把它和前后几天拼起来后，平均值可能上升也可能下降，甚至被稀释。长度一旦上下浮动，局部最优和全局最优之间的关系就变得非常不直观。

所以，对付平均值问题，大家通常不会正面硬刚，而是把目标值当成一个参数，去问“存不存在一个合法区间，它的平均值至少是 x”。这个问题好回答，后续再通过二分把 x 逼近到最优值。

2. 二分答案的底层逻辑：把“求最值”变成“判可行”

2.1 单调性是二分的前提

要二分一个东西，必须保证可行性随着 x 的变化是单调的。对于这里的“是否存在长度为 [L, R] 的区间，其平均值 ≥ x”，单调性非常自然：

• 如果当前 x 比较小，那么几乎任何稍微好一点的区间都能满足；
• 如果 x 越来越大，满足条件的区间会越来越少；
• 最优答案 ans 就处在临界点：当 x ≤ ans 时，一定存在区间满足（最优区间本身就是一个候选）；当 x > ans 时，所有合法区间的平均值都小于 x，判定必然失败。

所以“是否可行”这个布尔函数关于 x 是单调下降的。我们可以二分 x，然后每次用 O(N) 的 check 函数判断：x 如果可行，说明最优平均值至少是 x，于是把二分下界往上抬；反之把上界往下压。

2.2 关键一步：把所有值都减去 x，除法就消失了

现在的问题是：怎么在限定长度内，快速判断是否存在区间满足“平均值 ≥ x”？

这里有一个非常漂亮的小把戏。区间 [l, r] 的平均值 ≥ x，等价于：

(a[l] + a[l+1] + ... + a[r]) / (r - l + 1) ≥ x

两边乘以长度，变成：

(a[l] - x) + (a[l+1] - x) + ... + (a[r] - x) ≥ 0

换句话说，我们把数组里的每个数都统一减去 x，然后看这个“新数组”里是否存在一个长度在 [L, R] 之间的连续子段，其和 ≥ 0。除法被消掉了，问题从“算平均值”变成了“算区间和”。看起来只是一个简单的移项，但它把所有问题都拉回到了我们熟悉的前缀和领域。

2.3 前缀和视角下的重新表述

设新数组 b[i] = a[i] - x，再定义前缀和：

s[0] = 0 s[i] = s[i-1] + b[i] = (a[1] - x) + (a[2] - x) + ... + (a[i] - x)

那么区间 (l, r] 的和就是 s[r] - s[l-1]。为了方便，我习惯把“左端点”理解成“左端点的前一个下标 i = l-1”。于是判定问题变成：

是否存在下标 i 和 j，满足 0 ≤ i < j ≤ N，且区间长度 j - i 介于 [L, R]，并且 s[j] - s[i] ≥ 0。

如果存在，说明有某个合法区间的平均值能达到 x，check 返回 true，否则返回 false。到这里，判定问题的框架已经成型，剩下的核心就一个：在 N 这么大、区间长度还有上下限的情况下，怎样快速找出一对满足条件的 (i, j)。

3. 单调队列救场：把枚举左端点的成本从 O(N) 压到 O(1)

3.1 固定右端点后，左端点落在一个滑动窗口里

假设我们现在枚举右端点 j，那么所有能和 j 配对的左端点 i 必须满足：

j - R ≤ i ≤ j - L

也就是说，i 在一个长度为 R - L + 1 的窗口内。为了让 s[j] - s[i] 尽量大，我们希望在窗口内找到尽量小的 s[i]。窗口内 s[i] 的最小值一旦拿到，就能立刻判断 s[j] 减去这个最小值是否 ≥ 0。

注意，当 j 每次增加 1 的时候，窗口的左边界和右边界都会同时向右挪一位：

• 新的 i 上界变成 j - L，是一个新进入候选范围的下标；
• 旧的 i 下界变成 j - R，可能会有一些下标被甩出窗口。

这不就是标准的滑动窗口最值问题吗？只不过这里求的是“窗口内前缀和 s[i] 的最小值”，而不是最普通的“窗口内数组值的最值”。维护这种最值的经典数据结构就是单调队列。

3.2 单调队列到底在维护什么

单调队列的核心思想是：如果队列里出现了一个“下标更靠右、s 值又更小”的元素，那么之前所有“下标靠左、s 值还不占优”的元素，都永远没有机会成为最优解。

为什么？因为对任意一个未来的右端点 j，它要考虑的候选左端点窗口只会越来越靠右。一个下标更大的候选点，不仅比老候选点晚过期，也就是能存活更久，而且它的 s 值还更小，意味着在同样作为左端点时能让 s[j] - s[i] 更大。无论从哪个角度看，老候选点都比不过这个新来的，留着也没用，直接弹出队尾即可。

具体到这道题的 check 函数，维护规则是这样的：

1. 每当 j 增大，先把新进入窗口的下标 idx = j - L 加入队列。加入前，从队尾开始弹出所有 s[q[tail]] ≥ s[idx] 的下标，因为新下标更晚过期且 s 值更小（或相等），队尾那些旧下标失去了价值；
2. 然后从队头弹出所有 q[head] < j - R 的下标，因为它们已经滑出了合法的窗口范围；
3. 此时队头下标就是窗口内 s[i] 最小的那个，用它计算 s[j] - s[队头] 是否 ≥ 0。

这里有一个很多人第一次写容易踩的误区：队列里存的是“前缀和的下标”，不是前缀和的值。比较时拿 s[下标] 来比较，但真正入队、出队、过期判断的对象都是下标。下标这个概念代表的是“区间左端点的前一个位置”，它的取值范围和长度限制直接相关，不能搞混。

3.3 一个手动推演，帮助理解窗口滑动

举个简单例子。假设 L = 2，R = 3，当前 j = 5，那么这个右端点允许的左端点 i 只能是：

• j - R = 2，对应区间长度 3；
• j - L = 3，对应区间长度 2。

所以候选范围是 [2, 3]。当 j 变成 6 时，候选范围变成 [3, 4]：原来的下标 2 被弹出，新的下标 4 被加入。整个过程就是一条流水线，窗口匀速右移。

在代码实现上，很多人喜欢先将 0 这个下标预先放进队列，想着反正长度为 L 时可以从头开始取。这个习惯在小数据上可能没问题，但一旦 L 很大，比如 L=5、当前 j=1，根本没有任何合法区间，可队列里如果永远躺着 0，就会误把 s[1] - s[0] 当成一个长度为 1 的候选，而这个长度根本不满足下限要求。所以比较稳妥的写法，是从空队列开始，只在 j - L ≥ 0 的时候才把下标 j - L 放进去。

4. check 函数的完整实现与三个常见翻车点

4.1 一份可以直接复制的 C++ 代码

下面这份代码用“原始前缀和 pre 减去 x * i”来算修正后的前缀和，比每次累加 a[i] - x 的浮点误差更小。二分固定迭代 60 次，避免用 eps 判断可能带来的死循环问题。

#include <cstdio> #include <algorithm> using namespace std; const int MAXN = 100005; int n, L, R; int val[MAXN]; long long pre[MAXN]; // 原始数组前缀和，用 long long 防溢出 double b[MAXN]; // 修正后的前缀和：pre[i] - x * i int q[MAXN]; // 单调队列，存的是下标 bool check(double x) { for (int i = 1; i <= n; ++i) { b[i] = (double)pre[i] - x * i; } int head = 0, tail = -1; // 空队列 for (int j = 1; j <= n; ++j) { // 新进入合法范围的左端点是 j - L if (j - L >= 0) { int idx = j - L; while (head <= tail && b[q[tail]] >= b[idx]) --tail; q[++tail] = idx; } // 弹出已经小于 j - R 的过期下标 while (head <= tail && q[head] < j - R) ++head; // 窗口内最小 b[i] 就是队头 if (head <= tail && b[j] - b[q[head]] >= 0) { return true; } } return false; } int main() { scanf("%d%d%d", &n, &L, &R); for (int i = 1; i <= n; ++i) { scanf("%d", &val[i]); pre[i] = pre[i - 1] + val[i]; } double lo = -1e7, hi = 1e7; for (int t = 0; t < 60; ++t) { double mid = (lo + hi) / 2.0; if (check(mid)) lo = mid; else hi = mid; } printf("%.3f\n", lo); return 0; }

4.2 翻车点一：队列初始化的哨兵问题

我前面已经提过，不要在 check 一开始就把下标 0 放进队列。表面上 0 代表“左端点在数组开头之前”，好像天然合理，但在某些轮次里下标 0 并不在合法窗口内。以 L=3 为例，右端点 j=1 时，合法长度至少是 3，根本没有左端点能和它配对。可如果你预先把 0 放进去，代码会看到 b[1] - b[0]，误以为存在一个长度为 1 的合法区间，直接返回 true，二分结果就全错了。

正确姿势是：队列保持为空，只有当下标 j-L 真的进入窗口时才加入。你会问，那长度为 L 的区间怎么覆盖？比如 j=L 时，j-L=0，加入 0，此时 b[j]-b[0] 恰好就对应从第一天开始的长度为 L 的区间，合法且正确。

4.3 翻车点二：二分下界必须允许负数

产奶量可以是负数，所以平均值的真实最优答案完全可能是负数。如果你习惯性地把二分下界设成 0，那么当所有合法区间的平均值都是负数时，二分永远无法收敛到正确答案。

正确做法是让二分范围覆盖整个可能取值区间。根据输入数值范围，下界可以设成 -1e7、-1e9 甚至更小，上界同理。最保险的办法是直接取数组最小值作为下界、最大值作为上界，这样永远不会漏掉答案，而且二分次数多一点也能压到足够精度。

4.4 翻车点三：用固定迭代次数代替 eps 浮点比较

很多人写实数二分会写 while (hi - lo > eps)，然后设 eps = 1e-7。这个写法不是不行，但容易出两个问题：一是初始范围很大时，需要很多轮才能压到 eps，可能超时；二是 eps 设太小，达到 double 的精度极限后 hi - lo 不再稳定下降，可能出现死循环。

我的建议是直接在代码里写：

for (int t = 0; t < 60; ++t) { double mid = (lo + hi) / 2.0; if (check(mid)) lo = mid; else hi = mid; }

60 次二分在 double 上已经压得非常深，通常 40 次就足够，60 次图个放心。输出保留三位小数时，二分 60 次的精度富余量远大于需求，完全不用担心。

5. 从“假期”延伸出去：一套可以反复套用的解题框架

5.1 同样的模型换个马甲

“长度在 [L, R] 之间的连续区间，最大化区间平均值”这个模型，在各类算法题里非常常见。你可能会看到这些变体：

• 长度恰好为 K 的最大平均值子数组：直接滑窗维护长度为 K 的窗口和，不需要二分；
• 长度不超过 K 的最大平均值子数组：本质上就是 [0, K] 的长度限制，照样二分 + 单调队列，只是窗口左边界固定为 0；
• 长度在 [L, R] 之间的最大子段和（不除长度）：这个不用二分，直接把所有数当作 b[i]，一遍枚举右端点、单调队列维护窗口内最小前缀和即可；
• 二维矩阵中找一个面积在 [L, R] 之间的子矩阵，最大化平均灰度或其他值：枚举行上下边界，把列上的值压缩成一维数组，再跑一维的二分 + 单调队列。

识别这类题有个很直观的信号：题面里同时出现“连续区间 / 连续子数组”“长度至少 / 至多”“平均值最大 / 最小”这几个关键词。看到它们，脑内警报应该立刻响起。

5.2 相同的套路，不同的变着法考

第一类变化是长度限制的方向。原题是区间长度属于 [L, R]，实际操作时窗口上下界分别是 j-R 和 j-L。如果改成“长度至少 L”，那 R 相当于无穷大，窗口只需要处理下界；如果改成“长度至多 R”，那 L 相当于 0，窗口上界是 j，但要注意左端点 j 自己能不能取，取决于是否允许长度为 0 的空段。

第二类变化是判定不等号的方向。求最大平均值时，判定“是否存在区间平均值 ≥ x”对应着找窗口内 b[i] 的最小值。如果题目要求最小平均值，可以整体取相反数，也可以把判定改成“是否存在区间平均值 ≤ x”，这时需要找窗口内 b[i] 的最大值，单调队列维护的就是最大值而不是最小值。

第三类变化是数组的形态。如果数组变成环形的，比如“假期可以跨过年末年初”，通常的处理是复制一份数组、破环成链，长度为 2N，然后跑原来的算法，但要注意右端点 j 和左端点 i 的跨度不能超过 N，否则会算到同一个元素两次。这道题的原版没有这个陷阱，但换一道变体题就可能出现。

5.3 这个套路为什么值得反复练

我自己的体会是，二分答案 + 单调队列这套组合是很多“看起来很难”的题目的公共底盘。它考察的点其实很固定：

• 能不能把除法消掉，变成前缀和的比较；
• 能不能看出候选集合是一个滑动窗口；
• 能不能正确维护窗口内极值；
• 能不能把浮点数二分的边界条件写稳。

任何一个环节掉链子，整道题都会卡住。所以我在练习这类题时，会刻意把每一小步单独拆开去验证：先写一个暴力 O(N^2) 的 check 函数，拿它和单调队列版本在小数据上对拍；确认无误后，再去套二分框架。这样一旦出问题，能立刻定位到底是我“判定逻辑写错”还是“窗口维护写错”，而不会一锅粥地瞎猜。

回到 P2884 这道题本身，我觉得它最值得学习的地方就在这里。平均值、长度限制、负数数据、浮点二分，每个点单独拎出来都不难，但放在一起，就成了一个能区分“背模板”和“真理解”的经典题目。把它彻底吃透，再去碰那些迷宫一样的复杂变形题，你会觉得顺手很多。