1. 一次把题面说清楚平均气温到底要算什么先说结论这道题看起来是一道入门级的平均值统计题实际上换个角度就是“在一个序列里找满足大小关系的最长下标跨度”。我在写 PA8 的时候第一眼看到“Temperature”这个标题以为是给一堆温度算个平均数然后跟阈值比一比就完事了。真的动手测数据才发现题目要的不是“整段平均”而是“所有连续子段里平均气温不低于给定阈值的最长长度”。换句话说输入是一整年的逐日气温你要回答的并不是“今年平均多少度”而是“今年有没有一段持续 N 天以上平均气温能压在某个标准之上”。把问题换成人话就是给定一个长度为 N 的温度序列 A[1..N]再给一个阈值 T任意取一段连续的日子 [l, r]如果这一段的平均温度不低于 T我们就说这是一段合格的时期。现在要找出所有合格的时期里最长的那段包含了多少天找不到就输出 0。这种描述方式在工程上也有对应场景。比如结构健康监测里连续若干天的平均温度超过设计值就需要预警农业上要看“连续多少天日均温超过某个积温线”来决定播种窗口哪怕是你自己写代码处理传感器数据也经常会遇到“哎我要找最长的一段均值在某个范围里”的需求。所以这道题虽然名字朴素背后的思路拆开之后能用到不少地方。我拿到题面后先手算了一个小例子。假设 N 5T 20温度序列是15 21 20 19 22肉眼扫一遍最长的合格段是 [21, 20, 19, 22]合计 82平均 20.5长度为 4。有个细节容易漏如果把 [15, 21, 20, 19, 22] 整个拿来看平均值是 19.4不合格所以答案不能是 5。如果题目不问最长而是问“有没有长度 4 的合格段”那你还得先去验证 [15, 21, 20, 19] 或者 [21, 20, 19, 22] 这些子段。第二个例子用来提醒自己“大于等于”里的等号到底算不算。如果 N 2T 20温度是10 30那么整段平均值是 (1030)/2 20正好等于阈值 T。因为题面说的是“不低于”也就是 ≥所以这段长度 2 是合法答案。很多人在这个等号上翻车后面我会专门说边界怎么处理。这道题的输入规模通常不会太小。我按常见出题习惯估了一下N 大概可以到 10^5 甚至 10^6A[i] 和 T 都是整数温度值还有可能是负数。负数很重要因为后面做前缀和的时候负数会打破很多人的直觉甚至让双指针算法直接失效。所以严格点说这道题的核心不是“平均”而是“长度”。平均值只是给出一个判定条件真正的挑战在于你要在众多连续子段里快速找到满足条件的最长一段。2. 先写暴力O(N^2) 的枚举为什么能帮后期对拍拿到题先别急着上高深算法老老实实把暴力写出来至少有两个好处第一小数据你能靠它得到正确答案第二后面写优化版本的时候可以用它生成随机数据做对拍找出优化版到底在哪些隐蔽数据上写错了。暴力思路很简单枚举左端点 l再枚举右端点 r计算区间和然后判断区间平均值是否 ≥ T。为了不引入浮点数误差一般不用sum / len T这种写法而是把它改写成sum T * len。不过要注意T 和 len 的乘积可能超出 32 位整数范围尤其在 Python 里无所谓在 C 里一定要开 long long。一段暴力代码大概长这样def brute(n, T, a): ans 0 for l in range(n): s 0 for r in range(l, n): s a[r] length r - l 1 if s T * length: ans max(ans, length) return ans这个代码做的是对的但复杂度是 O(N^2)。当 N 到 10^5 的时候循环次数就是 10^10 这个量级完全没救当 N 到 10^6更是连碰都不能碰。不过它作为对拍基准非常合适我会在写完优化算法之后拿它跟优化算法跑几千组随机小数据逐一核对答案。还有一个小技巧暴力代码中判断条件里已经隐含了一个很重要的数学等价关系我先把结论放在这里下一节推导。这个等价关系几乎就是整道题的分水岭看懂了它后面的一切都是顺水推舟。你可能觉得“先写暴力再写优化”是多余的流程但实际上很多竞赛和工程里的坑恰恰是优化代码写得太顺结果样例过了随机数据一跑就挂。暴力就是那个帮你兜底的参考答案。我个人的习惯是只要时间允许先暴力后优化再写一个对拍脚本让两个程序在随机数据上跑一万次。这道题我后来果然靠对拍抓到了一个边界错误后面会展开讲。3. 关键转化把“平均值不低于 T”写成一行前缀不等式暴力写的没问题但 O(N^2) 不行必须想一个能压到 O(N) 的办法。这里最核心的一步是先把“平均值”这个带除法的条件改写成“差值和”的条件。考察一个连续区间 [l, r]长度记为 len r - l 1区间内温度总和为 S。题目要求S / len T两边同时乘以 len由于 len 一定是正数不等号方向不变S T * len再把右边展开到每一项就是A[l] A[l1] ... A[r] T T ... T移项合并(A[l] - T) (A[l1] - T) ... (A[r] - T) 0这一步看起来只是代数变形但它直接把问题从“平均值”变成了“差分后区间和是否非负”。我在这里的做法是先构造一个新数组 B[i] A[i] - T然后问B 数组里哪一段连续子数组的和大于等于 0且长度最长。这里面还有一个隐藏的好处不再需要处理除法跟浮点数了。如果直接判断平均值温度可能是负数平均值可能是小数光精度问题就能烦死你。用 B 的区间和所有数都是整数比较就是单纯的和 0 比干净利落。再进一步区间和问题天然适合前缀和。定义前缀数组 P[0] 0P[i] P[i-1] B[i]。那么区间 [l, r] 的和就是 P[r] - P[l-1]。条件就变成P[r] - P[l-1] 0也就是P[r] P[l-1]到这里整个问题就变得清晰了在数组 P 里面找一对下标 i j满足 P[j] P[i]然后让 j - i 最大。注意这里的 i 对应的是 l-1j 对应的是 r所以区间长度就等于 j - i。因为区间至少要有 1 个元素所以 i 和 j 必须满足 i j并且 j 的取值范围是 1 到 Ni 的取值范围是 0 到 N-1。用刚才的样例验证一下。N 5T 20A [15, 21, 20, 19, 22]B [-5, 1, 0, -1, 2]前缀 P 为P[0] 0 P[1] -5 P[2] -4 P[3] -4 P[4] -5 P[5] -3我们要找的是下标跨度最大的 ij 且 P[j] P[i]。肉眼扫P[5] -3P[1] -5满足跨度 4正是答案。P[5] 和 P[0] 比较-3 0 不成立所以不能取整个数组。逻辑完全对上了。这一步转化之后题目就不再是“温度”问题了而是一个“前缀数组上找满足偏序关系的最大下标距离”问题。很多乍看毫无头绪的题最后都是被这样一层一层“翻译”成简单模型的。也正因为这个原因我才觉得这道 PA8 值得写一篇比较完整的题解它把平均数、前缀和、单调性、贪心几样东西一次性串起来了。4. 用单调栈收编左端点哪些起点永远当不了答案现在问题已经变成给一个数组 P[0..N]找一对下标 ijP[j]P[i]且 j-i 最大。最朴素的做法还是 O(N^2)枚举所有左端点 i枚举所有右侧的 j判断条件。要优化我第一反应是“能不能用双指针滑动窗口”。可惜这里有个天真的陷阱P 数组并不是单调的。比如刚才的例子P 是 0, -5, -4, -4, -5, -3中间有升有降。窗口从左往右滑的时候你没法保证右边界往前扩展时左边界也可以安全地往前提。双指针要求窗口满足单调性这里不满足所以直接放弃。那怎么办换一个角度先分析哪些左端点 i 根本没资格参与答案。假设有两个下标 i1 和 i2满足 i1 i2而且 P[i1] P[i2]。也就是说i1 在左边并且前缀值还更小或者相等。那么对于任意一个在它们右边的下标 j只要 P[j] P[i2]必然也有 P[j] P[i1]。换句话说i2 能匹配到的所有 ji1 都能匹配到。而在长度上i1 更靠左于是 j - i1 一定大于 j - i2。那 i2 有什么存在意义没有在最优解里它永远不可能成为左端点。反过来如果 i1 i2 但 P[i1] P[i2]那 i1 和 i2 各有各的价值i1 靠左但是前缀值大i2 靠右但是前缀值小。到底哪个更好取决于最终的 j 在哪所以两个都得留着。这个逻辑给出一套很干脆的筛选规则从左往右扫描 P 数组维护一组候选左端点下标要求它们的前缀值严格递减。每当遇到一个 P[i]如果它不比当前最后一个候选的前缀值小就说明它被已有的某个更左候选“支配”了可以直接丢掉不加入候选集合如果它比最后一个候选的前缀值小就说明它是一个新的低谷应该放进候选集合。具体实现可以用栈。规则就是stack [] for i in range(n 1): if not stack or P[i] P[stack[-1]]: stack.append(i)每步判断用的是严格小于不是小于等于。为什么要严格如果 P[i] 和栈顶一样大那新下标更靠右前缀值却一样它也无法在任何答案里胜过更靠左的旧下标所以同样被支配没必要入栈。拿刚才的 P 数组过一遍P [0, -5, -4, -4, -5, -3]i0P[0]0栈空入栈栈为 [0]i1P[1]-5-5 0入栈栈为 [0, 1]i2P[2]-4-4 -5 不成立丢弃i3P[3]-4-4 -5 不成立丢弃i4P[4]-5-5 -5 不成立注意这里是严格小于相等也丢弃i5P[5]-3-3 -5 不成立丢弃最后候选左端点只剩两个0 和 1。栈里下标递增前缀值递减在示例里恰好形成了一个从 0 到 -5 的下降序列。这里有个直觉可以分享你其实是在维护一个“阶梯型”的候选列表。越靠左的候选前缀值必须越大越靠右的候选前缀值必须越小。这样每个候选都代表着一个潜在的“低位买入”机会越往右买入价越低但右侧的空间也变少了。最后答案一定是从某个候选出发向右找到一个足够高的“卖出点”让两个位置距离最远。构建候选集合这一步的复杂度是 O(N)因为每个下标最多入栈一次。5. 反向扫描挤出最长跨度主算法与正确性推敲候选左端点已经筛好了现在的问题是怎么配合右端点 j快速算出最大跨度。我先把算法流程写出来然后再解释为什么它是对的。ans 0 for j in range(n, 0, -1): while stack and P[j] P[stack[-1]]: ans max(ans, j - stack[-1]) stack.pop()注意这里 j 的枚举顺序是从右往左而不是从左往右。设计成这样是有原因的。假设当前考察某个右端点 j栈顶是所有候选左端点里最靠右的那一个记为 top。如果能满足 P[j] P[top]那么对当前这个 j 来说能跟它匹配的候选里跨度最大的一定是栈顶因为栈顶下标最大。所以我们先用 top 更新答案然后直接把 top 弹出栈不再留它。为什么要立刻弹出这里的思考是我们已经找到了一个 j它比 top 的前缀值大。对于更靠左的右端点 j也就是 j j即使 P[j] P[top] 依然成立j - top 也不会超过 j - top。换句话说top 能产生的最优跨度已经在当前 j 这里实现了未来的任何 j 都不可能用 top 做出更大的答案。所以 top 的使命结束可以安全弹出。弹出 top 之后新的栈顶变成上一个候选。如果 P[j] 仍然能盖过这个更左的候选说明它在当前 j 这里也能匹配而且跨度比刚才更长。那我们就继续弹出继续更新答案。一直弹到栈空或者 P[j] 小于栈顶前缀值为止。如果 P[j] 小于栈顶前缀值说明当前 j 连最靠右的候选都匹配不上那些更靠左、前缀值更大的候选就更匹配不上。因此当前 j 不是一个有效的右端点直接跳过去看 j-1。用刚才的示例手动跑一遍P [0, -5, -4, -4, -5, -3]栈是 [0, 1]j5P[5]-3栈顶是下标 1P[1]-5。-3 -5更新 ans 5-1 4弹出 1。此时栈为 [0]栈顶 P[0]0。-3 0 不成立停止。j4P[4]-5栈顶 P[0]0-5 0 不成立。j3P[3]-4同样不成立。j2P[2]-4不成立。j1P[1]-5不成立。最终 ans 4跟暴力结果一致。再试一下等号边界。N2T20A[10,30]B[-10,10]P[0,-10,0]。构建候选栈P[0]0 入栈P[1]-10 入栈P[2]0不小于 -10丢弃。栈为 [0,1]。反向扫描j2P[2]0栈顶 P[1]-100 -10更新 ans1弹出 1现在栈顶 P[0]00 0 成立更新 ans2弹出 0。最终答案是 2正确。注意上面第二步用到了等号这正是我前面提醒过的“不低于”三个字的含义。如果题目改成“严格高于 T”等号那步就不该更新写法要换成P[j] P[stack[-1]]。这个算法的正确性用一句话概括就是候选栈保证每个被弹出的左端点都已经在自己最长可能的位置上完成了使命从右往左枚举右端点保证每次弹出的 left都是以它能匹配到的最右端点来结算。任何没有弹到、后来被更左端点结算的情况都不会比已经弹出的答案更好因为更左意味着跨度更小。整个过程里每个下标最多入栈一次也最多出栈一次所以反向扫描同样是 O(N)。两部分合起来总复杂度 O(N)。6. 代码落地两个版本的实现与三种必踩的边界理论讲完该上代码了。我平时写题解习惯把 Python 和 C 都放出来因为这两种语言在这道题上的写法没有本质区别但输入输出和整数溢出的处理差异比较大。先看 Python 版本重点是大数据输入要用 sys.stdin.buffer.readimport sys def main(): data sys.stdin.buffer.read().split() if not data: return n int(data[0]) T int(data[1]) a list(map(int, data[2:2 n])) pref [0] * (n 1) for i in range(1, n 1): pref[i] pref[i - 1] (a[i - 1] - T) stack [] for i in range(n 1): if not stack or pref[i] pref[stack[-1]]: stack.append(i) ans 0 for j in range(n, 0, -1): while stack and pref[j] pref[stack[-1]]: ans max(ans, j - stack[-1]) stack.pop() print(ans) if __name__ __main__: main()再写一个 C 版本方便那些习惯写 C 的朋友#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; long long T; cin n T; vectorlong long a(n 1); for (int i 1; i n; i) { cin a[i]; } vectorlong long pref(n 1, 0); for (int i 1; i n; i) { pref[i] pref[i - 1] (a[i] - T); } vectorint st; for (int i 0; i n; i) { if (st.empty() || pref[i] pref[st.back()]) { st.push_back(i); } } long long ans 0; for (int j n; j 1; j--) { while (!st.empty() pref[j] pref[st.back()]) { ans max(ans, (long long)j - st.back()); st.pop_back(); } } cout ans \n; return 0; }代码本身不长但有几个边界问题我挨个说一下都是实际写挂了才长记性的地方。第一个边界是空区间。如果所有温度都低于 T比如 A [10, 20]T 30那么不存在任何合格区间答案应该是 0。暴力代码天然返回 0优化代码要确保 ans 初始为 0并且知道自己不会在负数条件下误更新。你可以在纸上跑一下B [-20, -10]P [0, -20, -30]候选栈是 [0, 1, 2]反向扫描时 P[j] 从 -30 一路升到 0始终盖不过栈顶ans 保持 0正确。第二个边界是 j 的范围必须从 n 到 1不能从 n 到 0。如果把 j 0 也纳入扫描会出现 P[0] P[0] 的情况然后更新 ans 0 - 0 0虽然不影响最终最大值但逻辑上不对。更危险的是如果 P 数组开头有负数栈j0 和栈里某些下标比较会算出合法的负数跨度虽然不会更新 ans但可能导致你对算法过程理解出偏差。严谨起见右端点至少是区间右端而区间长度至少为 1所以 j 从 1 开始。第三个边界是整数类型。C 里 A[i] 和 T 都可能比较大A[i] - T 乘以 N 之后很容易超过 int 范围必须用 long long。我见过不少人在这里没有用 long long结果小数据全对一到大数据就出负数排查半天发现是溢出。Python 不用考虑溢出这也是我推荐初学者先用 Python 理解算法、再切回 C 写高并发场景的原因不过这只是个人习惯。还有一个小细节构建候选栈时用的是pref[i] pref[stack[-1]]严格小于。如果温度恰好让前缀值相等右侧的这个下标会被丢弃。这个设计刚说过因为相等时它完全被左侧下标支配。别手滑写成小于等于否则候选栈里会多出一批永远没必要保留的下标虽然答案一般不会错但算法就不那么“干净”了。7. 复杂度总结这类题目还能往哪边扩展最后把理论性能做个汇总。构建前缀数组 O(N)构建候选栈 O(N)反向扫描 O(N)所以总时间复杂度 O(N)空间上只需要前缀数组和栈结构都是 O(N)。在 N 10^6 的时候这个方案跑起来很轻松在实际验证中我用随机数据连续跑了几千组优化版本和暴力版本答案完全一致只有极少数等号边界场景需要小心核对最终也都通过了。我复盘这道题的时候最大的收获不是那个单调栈写法本身而是“平均数条件 → 差分前缀数组 → 最大跨度”这条翻译链路。很多题目表面上是一套规则本质上是另一套规则。一旦你把题面条件改写成前缀数组的不等式原来搜肠刮肚也想不到的优化可能就顺着数据结构自然浮现出来了。这个思路能迁移的地方也不少。比如把阈值 T 变成一个函数每天阈值不同B 数组就变成 A[i] - T[i]剩下的逻辑几乎不用动。再比如题目改成“找出最短的一段使得平均气温低于某个值”照样可以翻译成前缀差问题只是反向扫描和候选栈的构造方向要调整一下。甚至温度换成股价、传感器数值、或任意整数序列这个模板都能直接用。如果想进一步挑战自己可以试试把 N 上限加到 10^7然后要求空间也压到 O(1) 辅助空间。这时你会发现前缀数组都能省掉因为候选栈可以用“只记录位置而不记录前缀值”的方式压缩或者把前缀值算出来后直接只保留极小值点。不过这属于后话能把本题的 O(N) 版本写对PA 系列这道题的核心分就已经拿到了。我自己的体会是这类题目最忌讳一上来就背模板。先手动推两遍示例把前缀不等式写出来再想为什么单调栈能筛掉冗余候选最后再去写代码顺手很多。如果直接把网上搜到的代码复制过来样例过了也糊里糊涂下次碰到换皮题还是会卡住。写题解的过程就是把自己曾走过的弯路记录一遍希望对同样卡在这道题的人有帮助。
