企业官网建设流程全解析

华为OD机考C卷的算法题里，几何平均值最大子数组算是一道很典型的“一看就会、一写就废”的题目。备考那阵子我在这道题上反复折腾了几个晚上，第一次用双层循环枚举区间，样例直接能过，心里还挺美，结果一提交面对大 n 的测试点，超时超到怀疑人生。后来老老实实从数学性质重新推了一遍，才发现这道题的钥匙不是“怎么枚举”，而是“怎么把几何平均转化成可以前缀和处理的算术平均”。

这篇文章我会把这道题完整拆开讲：题目到底要我们算什么、为什么朴素枚举不行、取对数之后怎么变成二分答案、以及 Java、Python、JS、Go、C++、C 六种常见机考语言的完整实现和注释。最后再把我实际刷题和模拟机考时踩过的坑整理成速查表，想备战华为OD机考、或者单纯想练二分答案题型的同学，都可以直接照着走一遍。

1. 先从题目说起：几何平均值最大子数组到底在问什么

1.1 题目描述与输入输出形式

华为OD机考的双机位C卷里，这道题一般是这样描述的：给定一个长度为 n 的正整数数组 a，再给定一个最小长度 L，题目要求找到一个长度不小于 L 的连续子数组，使得这个子数组内所有元素的几何平均值最大，并输出这个最大几何平均值。

几何平均值的公式是：

GM = (a[l] * a[l+1] * ... * a[r]) ^ (1 / (r - l + 1))

也就是先把区间内所有数乘起来，再开“区间长度”次方。需要注意，这里不是算术平均，算术平均是加起来除以个数，几何平均则是连乘再开方。

看一个最简单的样例。

输入： 5 2 1 2 3 4 5

输出： 4.472136

这个输出是怎么来的？所有长度至少为 2 的连续子数组里，几何平均值最大的是 [4, 5]，计算得到 sqrt(4 * 5) ≈ 4.472136。有时候题目会要求保留六位小数，具体以题干说明为准。

这道题适合所有准备OD机考的候选人，尤其是C卷偏算法方向的岗位。它的核心考点非常集中：一是能否识别出几何平均值不适合直接枚举，二是能否想到用对数变换把乘法问题转化为加法问题，三是能否熟练写出二分答案加前缀和判定的框架。这三个能力，正是机考算法题筛人最常用的几个点。

1.2 为什么朴素枚举不可行

我第一版代码写得很直接：枚举左端点 i，再从 i 到 n 枚举右端点 j，只要长度满足 j - i + 1 >= L，就暴力连乘再开方，维护一个最大值。在 n 特别小的时候这当然没问题，但机考的 n 经常给到 10^5 甚至更高，O(n^2) 的枚举量直接到 10^10 这个量级，几秒甚至几十秒都跑不完。

就算不考虑时间复杂度，暴力连乘也有一个隐患：区间长度大时乘积会非常巨大，就算用 double 也可能溢出或者丢失精度。比如 100 个 10000 相乘，数值已经是天文数字，double 根本扛不住。虽然开根号后数值会回到合理范围，但中间过程的溢出已经让结果不可信了。

所以这道题的难点不在“能不能求出来”，而在“怎么高效、数值稳定地求出来”。这里的突破口，就是几何平均值本身蕴含的数学性质。

2. 核心思路：取对数把几何平均变成算术平均

2.1 对数变换与单调性

对数运算有一条非常关键的恒等式：

log(A * B) = log(A) + log(B)

把它用在几何平均值上，可以得到：

log((a[l] * a[l+1] * ... * a[r]) ^ (1 / len)) = (1 / len) * (log(a[l]) + log(a[l+1]) + ... + log(a[r]))

这个变换的意义很大：几何平均值的对数，等于每个元素取对数后的算术平均值。

也就是说，原数组上求几何平均值最大的子数组，等价于先把每个元素取对数，得到一个新数组 b[i] = log(a[i])，然后在这个新数组上找一个长度至少为 L 的连续子数组，使其算术平均值最大。最后再把得到的最大算术平均值做一次指数运算 exp(x)，还原成几何平均值。

这个过程跟声音用分贝表示很像：声音强度本身是成倍增长的，直接算起来数字跨度太大，取对数之后反而变得更直观、更容易比较。对数变换就是把乘法世界中不好处理的“乘积”，映射成加法世界中好处理的“和”。

2.2 二分答案 + 前缀和判定

现在问题变成了：给定数组 b，长度 n，最小长度 L，找一个长度至少为 L 的连续子数组，使算术平均值最大。

这类“求最大平均值子数组”的问题，有一个很成熟的套路：二分答案。我们不直接去枚举所有区间，而是猜测一个平均值 mid，然后判断“是否存在一个长度至少为 L 的连续子数组，其平均值大于等于 mid”。

如果存在这样的子数组，说明答案还可以更大，把二分的下界往上调；如果不存在，说明 mid 猜大了，把上界往下调。判断存在性的过程，可以在 O(n) 内完成。

具体怎么判断呢？对于猜测的 mid，我们要检查是否存在长度至少为 L 的区间，满足：

(sum(b[i]) / len) >= mid

两边都乘以 len，等价于：

sum(b[i]) >= len * mid

再移项：

sum(b[i] - mid) >= 0

所以只要把原数组每个元素都减去 mid，然后看是否存在长度至少为 L 的连续子数组，其和大于等于 0 即可。

判断“是否存在长度至少为 L 的连续子数组的和大于等于 0”，可以用前缀和来优化。定义 pref[i] 为前 i 个元素的累加和，那么区间 [l, r] 的和就是 pref[r] - pref[l-1]。枚举右端点 r，只要在它左边找到一个尽量小的前缀和，如果 pref[r] - minPref >= 0，就说明存在满足条件的区间。

这里有一个很容易写错的地方：因为要求区间长度至少为 L，所以当右端点枚举到 r 时，左端点的前一个位置 l-1 最大只能是 r - L。也就是说，可用的前缀和 pref[l-1] 的下标范围是 0 到 r - L。我们需要维护这个范围内的最小值 mn，然后判断 pref[r] - mn >= 0。

可以用一个小表格来理解 mn 的更新过程：

可以看到，每向右移动一次右端点，可用范围就会多一个 pref[r-L+1]。所以代码里在检查完当前右端点后，更新 mn 时用的是 pref[r-L+1]，而不是 pref[r] 或 pref[r-L]。这个索引差一的问题，是很多同学调试半天都过不了样例的元凶。

2.3 为什么可以二分：单调性证明

二分答案能成立的前提是判定函数具有单调性。对这道题来说，单调性非常直观：如果存在一个长度至少为 L 的子数组，它的几何平均值大于等于某个值 X，那么对于任意小于等于 X 的值 Y，这个子数组的几何平均值也一定大于等于 Y，所以判定函数“存在子数组的几何平均值大于等于 mid”是随着 mid 增大而单调递减的。

换句话说，mid 比较小时，判定结果基本为 true；mid 一直大到超过真实答案后，判定结果才会变为 false。我们要找的“最大的 true”，就是题目要求的最大几何平均值。

这种单调性是二分的理论保证。没有这个性质，二分就不可信。所以以后遇到类似“求最大值/最小值可行解”的题目，第一反应应该是先验证一下判定函数是否具备单调性，再决定能不能用二分。

3. 六种语言落地实现

3.1 Java 实现与解析

Java 是很多OD机考候选人的主力语言，它的优势是类库齐全、写起来结构清晰。机考环境一般用 Java 8 或 Java 11，所以我的实现尽量不依赖高版本特性。

import java.io.*; import java.util.*; public class Main { static int n, L; static double[] logs, pref; static boolean check(double mid) { pref[0] = 0; for (int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + logs[i - 1] - mid; } double mn = 0; for (int i = L; i <= n; i++) { if (pref[i] - mn >= 0) { return true; } mn = Math.min(mn, pref[i - L + 1]); } return false; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); n = Integer.parseInt(st.nextToken()); L = Integer.parseInt(st.nextToken()); logs = new double[n]; double lo = 1e18, hi = -1e18; st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { double v = Double.parseDouble(st.nextToken()); logs[i] = Math.log(v); lo = Math.min(lo, logs[i]); hi = Math.max(hi, logs[i]); } pref = new double[n + 1]; for (int iter = 0; iter < 80; iter++) { double mid = (lo + hi) / 2; if (check(mid)) { lo = mid; } else { hi = mid; } } System.out.printf("%.6f%n", Math.exp(lo)); } }

这里解析输入用的是 BufferedReader 加 StringTokenizer，而不是 Scanner。原因很简单：Scanner 在读取大量数据时会不断做正则解析，性能比 BufferedReader 差不少。机考数据量大的时候，输入快一点总是好的。

注意 Math.log(v) 要求 v 是正数，如果数组里出现 0 或负数，这里会直接报错或者返回 NaN。默认题目会给正整数，但如果你拿到的题目描述没明确，建议先处理特殊值。

3.2 Python 实现与解析

Python 写起来最省事，适合用来在草稿纸上快速验证思路。不过 Python 的常数项比较大，同复杂度下可能比 C++ 慢一些，所以输入处理和循环写法要稍微注意。

import sys import math def main(): data = sys.stdin.read().strip().split() if not data: return idx = 0 n = int(data[idx]) idx += 1 L = int(data[idx]) idx += 1 logs = [math.log(float(data[idx + i])) for i in range(n)] lo, hi = min(logs), max(logs) def ok(mid): pref = [0.0] * (n + 1) for i in range(1, n + 1): pref[i] = pref[i - 1] + logs[i - 1] - mid mn = 0.0 for i in range(L, n + 1): if pref[i] - mn >= 0: return True mn = min(mn, pref[i - L + 1]) return False for _ in range(80): mid = (lo + hi) / 2 if ok(mid): lo = mid else: hi = mid print(f"{math.exp(lo):.6f}") if __name__ == "__main__": main()

sys.stdin.read().strip().split() 一次性把整个输入读进来，然后按空白字符分割。这样可以兼容数组折行输入的情况，比一行一行 readline 更省心。

Python 的 min 函数每次调用都会有一点点开销，如果你追求极限性能，可以把 mn 的比较改成 if pref[i - L + 1] < mn: mn = pref[i - L + 1]。在 n 达到 10^5 且二分 80 次的场景下，这个微小的差异实际上能节省不少时间。

3.3 JavaScript 实现与解析

JS 在机考中一般跑在 Node.js 环境，输入输出用 process.stdin 和 console.log。JS 在写这类算法题时，最需要留意的是 parseFloat 的精度和 Math.log 的使用。

const readline = require('readline'); const rl = readline.createInterface({ input: process.stdin, output: process.stdout }); let lines = []; rl.on('line', (line) => { lines.push(line.trim()); }); rl.on('close', () => { const data = lines.join(' ').split(/\s+/).map(Number); const n = data[0]; const L = data[1]; const logs = data.slice(2, 2 + n).map(Math.log); let lo = Math.min(...logs); let hi = Math.max(...logs); const ok = (mid) => { const pref = new Array(n + 1).fill(0); for (let i = 1; i <= n; i++) { pref[i] = pref[i - 1] + logs[i - 1] - mid; } let mn = 0; for (let i = L; i <= n; i++) { if (pref[i] - mn >= 0) return true; if (pref[i - L + 1] < mn) mn = pref[i - L + 1]; } return false; }; for (let iter = 0; iter < 80; iter++) { const mid = (lo + hi) / 2; if (ok(mid)) lo = mid; else hi = mid; } console.log(Math.exp(lo).toFixed(6)); });

lines.join(' ').split(/\s+/) 的处理方式是为了兼容输入数据分成多行的情况。机考里有时候数组元素会莫名其妙换行，如果只按第一行读取，很容易漏数据。

Math.min(...logs) 在 n 特别大的时候可能超出 JS 引擎对函数参数数量的限制。稳妥一点的做法是在循环里手动找最小值和最大值，或者用 logs.reduce。如果 n 在 10^5 左右，展开运算符通常还能撑住，但为了保险，我更推荐动手写循环。

3.4 Go 实现与解析

Go 在算法题里出现频率越来越高，它的标准库功能直接，写起来也不拖泥带水。但 Go 的 bufio.Scanner 默认缓冲区有限，如果输入非常大，需要手动调大 buffer。

package main import ( "bufio" "fmt" "math" "os" "strconv" "strings" ) func check(logs []float64, n, L int, mid float64) bool { pref := make([]float64, n+1) for i := 1; i <= n; i++ { pref[i] = pref[i-1] + logs[i-1] - mid } mn := 0.0 for i := L; i <= n; i++ { if pref[i]-mn >= 0 { return true } if pref[i-L+1] < mn { mn = pref[i-L+1] } } return false } func main() { sc := bufio.NewScanner(os.Stdin) sc.Buffer(make([]byte, 1024*1024), 1024*1024) sc.Scan() first := strings.Fields(sc.Text()) n, _ := strconv.Atoi(first[0]) L, _ := strconv.Atoi(first[1]) logs := make([]float64, n) lo := 1e9 hi := -1e9 sc.Scan() nums := strings.Fields(sc.Text()) for i := 0; i < n; i++ { v, _ := strconv.ParseFloat(nums[i], 64) logs[i] = math.Log(v) if logs[i] < lo { lo = logs[i] } if logs[i] > hi { hi = logs[i] } } for iter := 0; iter < 80; iter++ { mid := (lo + hi) / 2 if check(logs, n, L, mid) { lo = mid } else { hi = mid } } fmt.Printf("%.6f\n", math.Exp(lo)) }

Go 这里需要注意 strconv.ParseFloat 返回的是 float64，math.Log 接受的也是 float64，类型上不会出问题。但如果数组元素可能分成多行输入，上述代码就有风险，因为 sc.Scan() 只读了一行。更稳妥的做法是写一个循环把所有 token 读完，再手动切分。

3.5 C++ 实现与解析

C++ 是机考中性能最稳的选择之一，也是很多追求极限速度的考生的首选。用 vector 存数组，代码量并不大。

#include <bits/stdc++.h> using namespace std; int n, L; vector<double> logs, pref; bool check(double mid) { pref[0] = 0; for (int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + logs[i - 1] - mid; } double mn = 0; for (int i = L; i <= n; i++) { if (pref[i] - mn >= 0) return true; mn = min(mn, pref[i - L + 1]); } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> L; logs.assign(n, 0); double lo = 1e18, hi = -1e18; for (int i = 0; i < n; i++) { double v; cin >> v; logs[i] = log(v); lo = min(lo, logs[i]); hi = max(hi, logs[i]); } pref.assign(n + 1, 0); for (int iter = 0; iter < 80; iter++) { double mid = (lo + hi) / 2.0; if (check(mid)) lo = mid; else hi = mid; } cout << fixed << setprecision(6) << exp(lo) << '\n'; return 0; }

C++ 里最容易忽略的是 ios::sync_with_stdio(false) 和 cin.tie(nullptr) 这两行。机考如果混用 cin 和 scanf，很可能出现数据没读完的情况。关闭同步后，cin 的读取速度会接近 scanf，性能足够。

另外，pref 数组每轮 check 都会被重新赋值，pref[0] 固定为 0，所以不需要在调用 check 前清空整个数组。这个细节虽然不影响正确性，但能省一点不必要的遍历时间。

3.6 C 实现与解析

C 语言实现最原始，也最容易暴露出对指针和数组下标的掌握程度。如果你习惯用 C 写机考题，代码里重点注意 scanf 的格式化符号和 math.h 的链接。

#include <stdio.h> #include <math.h> #define MAXN 100005 int n, L; double logs[MAXN]; double pref[MAXN]; int check(double mid) { pref[0] = 0; for (int i = 1; i <= n; i++) { pref[i] = pref[i - 1] + logs[i - 1] - mid; } double mn = 0; for (int i = L; i <= n; i++) { if (pref[i] - mn >= 0) { return 1; } double candidate = pref[i - L + 1]; if (candidate < mn) { mn = candidate; } } return 0; } int main() { scanf("%d %d", &n, &L); double lo = 1e18, hi = -1e18; for (int i = 0; i < n; i++) { double v; scanf("%lf", &v); logs[i] = log(v); if (logs[i] < lo) lo = logs[i]; if (logs[i] > hi) hi = logs[i]; } for (int iter = 0; iter < 80; iter++) { double mid = (lo + hi) / 2.0; if (check(mid)) lo = mid; else hi = mid; } printf("%.6lf\n", exp(lo)); return 0; }

C 实现的坑主要在 scanf 格式：读取 double 必须用 %lf，输出 double 用 %.6lf。如果写成 %f，在部分编译环境下读取会出错。另外，使用 math.h 里的 log 和 exp 时，有些评测机需要手动链接 -lm，具体看编译命令，本地调试时可以在编译指令里加上。

4. 数据复盘：复杂度、边界与为什么能过

4.1 时间复杂度与空间复杂度

这道题整体算法是二分答案套 O(n) 判定。二分次数我写的是 80 次，每次 check 都要遍历数组，所以总时间复杂度是 O(80 * n)，去掉常数就是 O(n log(MAX - MIN))，在 n = 10^5 时，约 800 万次循环，机考环境轻松通过。

空间复杂度是 O(n)，主要用来存原始数组取对数后的 logs 数组和前缀和 pref 数组。C 语言实现用静态数组也可以用动态分配，各语言大同小异。

固定二分 80 次比用 eps 来判断更推荐。浮点运算本身有误差，如果 while (hi - lo > 1e-7) 这种写法，极端情况下可能陷入死循环或者精度不够。固定 80 次，double 的精度足够收敛到 1e-18 的数量级，用来输出六位小数绰绰有余。

4.2 边界情况与数据范围推演

几个容易出问题的边界：

第一，L = 1。此时长度只要为 1 即可，几何平均值最大的子数组就是单个元素里最大的那一个，答案就是原数组的最大值。算法不需要特判，二分范围包含所有元素的对数值，判定函数也能正常返回，但如果你做题时想加一个快速判断，可以减少无用计算。

第二，n = L。整个数组就是唯一满足长度的子数组，答案就是整个数组的几何平均值。这种情况算法也能正确处理，因为判定函数只会检查长度为 L 的区间。

第三，所有元素相等。比如数组全是 7，那么所有子数组的几何平均值都是 7，二分最终会收敛到 log(7)，再指数运算还原成 7。这种情况考验的是浮点稳定性，固定 80 次不会出问题。

第四，数组中出现 0 或负数。对数函数在非正数上无意义，现实中一般题目会明确给正整数。如果你遇到的是变形题，需要单独处理 0 的情况，比如判断如果包含 0 且存在全零区间，答案可能是 0，但这已经超出本文默认题目的范围了。

5. 实战避坑：精度、输入输出与刷题心态

5.1 精度问题

很多第一次写这道题的人会在输出上栽跟头。明明本地算出来结果是 4.47213595，结果 OJ 输出要求 4.472136，如果直接 printf("%.5f") 少了位数，就是错误答案。

精度控制注意三点：数组元素取对数时统一用 double，不要用 float；二分迭代次数给足，建议 50 到 80 次，太少了可能收敛不到位；最后输出用 printf("%.6f") 或者等价写法按六位小数输出。

判定函数里比较 pref[i] - mn >= 0 时，理论上不会有太大问题，因为题目一般接受 1e-6 级别的误差。如果你遇到特别严格的卡精度题，可以把判断改成 pref[i] - mn > -1e-10，给自己留一点浮点误差的余量。

5.2 输入输出格式的坑

机考和本地 IDE 的最大区别是输入输出格式完全由评测系统控制。我见过不少同学本地样例跑得好好的，一到线上就各种诡异问题，最后发现是读取数据的方式太脆弱。

第一个坑：不要假设第二行一定是数组。数据可能跨行，也可能末尾有换行或空格。用 Java 的 BufferedReader + StringTokenizer、Python 的 sys.stdin.read().split()、JS 的 lines.join(' ') 这种按空白符切分的方式，可以最大程度避免这类问题。

第二个坑：输出一定要换行。有些语言 printf 不会自动加换行，C 和 C++ 需要显式写 '\n'，Java 用 printf("%.6f%n") 或者 println，Go 用 fmt.Printf 也要自己加 \n。

第三个坑：本地调试通过不代表线上判题通过。OD 机考的在线编译器可能对提交代码的类名、包名有要求，比如 Java 的 Main 类必须存在，否则直接编译错误。提前熟悉目标 OJ 的提交规范，不要到了考场上再踩。

5.3 双机位机考的应试建议

双机位机考要求考生在前后两个摄像头的监控下独立完成答题，这种环境对“代码能力”和“临场心态”的要求都更高。考试前一定要调试好摄像头、浏览器和网络，找一个光线充足、背景整洁的房间，避免考试中途因为环境问题被判违规。

从刷题角度来说，OD 机考的 C 卷算法题整体偏向经典题型，二分答案、动态规划、滑动窗口、栈和哈希表都是高频考点。几何平均值最大子数组这道题属于“数学变换 + 二分答案”的组合题，如果能在备考阶段把这类题的思路吃透，遇到类似题目就不会慌。

另外，机考时可以先快速浏览所有题目，挑有把握的先写，不要在一道题上死磕太久。如果卡住了，可以先写一个暴力版本拿部分分数，再逐步优化。

5.4 常见错误速查表

我自己刷这道题时踩过不少坑，也见过身边同学反复犯同样的错误，整理成一张表放在这里，考前一天过一遍非常有用。

最后再分享一个我个人的刷题心得：二分答案这类题，核心其实不是二分本身，而是“怎么设计一个单调的判定函数”。你只要能把判定函数想清楚，代码基本就成功了大半。几何平均值最大子数组最巧妙的地方在于取对数，这一步没有想通之前，后面所有操作都是在硬来。备考时建议把这道题从暴力版本到二分版本完整写两遍，第一遍理解思路，第二遍默写代码，等你能够不看任何参考一次通过的时候，这类题在机考里就真的稳了。