华为OD机试 新系统 统一考试题库清单持续收录中以及考点说明Python/JS/C/C。专栏导读本专栏收录于《华为OD机试真题Python/JS/C/C》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。一、题目描述从一个长度为N的正数数组numbers中找出长度至少为L且几何平均值最大的子数组并输出其位置和大小。K个数的几何平均值为K个数的乘积的K次方根若有多个子数组的几何平均值均为最大值则输出长度最小的子数组。若有多个长度相同的子数组的几何平均值均为最大值则输出最前面的子数组。二、输入描述第一行输入为N、L• N表示numbers的大小1 ≤ N ≤ 100000• L表示子数组的最小长度1 ≤ L ≤ N之后N行表示numbers中的N个数每个一行10-9≤ numbers[i] ≤ 109三、输出描述输出子数组的位置从0开始计数和大小中间用一个空格隔开。备注用例保证除几何平均值为最大值的子数组外其他子数组的几何平均值至少比最大值小10-10倍四、测试用例测试用例11、输入3 22232、输出1 23、说明候选子数组[2,2]几何平均值 2[2,3]几何平均值 √6[2,2,3]几何平均值 ∛12其中 [2,3] 最大所以输出起点 1长度 2。测试用例21、输入10 20.20.10.20.20.20.10.20.20.20.22、输出2 23、说明长度至少为 2 时最优是从下标 2 开始的 [0.2, 0.2]其几何平均值为 0.2。后面虽然也有很多 0.2,0.2但题目要求同值时取最前面的。五、解题思路1、为什么用二分查找“最大平均值子数组”是经典模型。假设我们二分一个答案 mid判断是否存在长度至少为 L 的子数组使得其平均值 mid。把每个元素变成c[i]b[i]−mid那么问题就变成是否存在长度至少为 L 的子数组其元素和 0。这个判断可以用前缀和在线性时间完成所以总复杂度就是二分约 80 次2、如何恢复最终区间二分出最大平均值后还要满足题目的额外规则几何平均值最大如果有多个取长度最小如果长度还相同取起点最靠前恢复区间时需要对每个右端点 j 找到i j-Lprefix[i] prefix[j]并且 i 尽可能大这样 j-i 最短这一步用前缀和离散化树状数组Fenwick Tree维护前缀范围内最大下标六、Python算法源码importsysimportmathimportbisect# 树状数组维护前缀范围内“最大的下标”classFenwickMax:def__init__(self,n):self.nn self.tree[-1]*(n2)defupdate(self,idx,val):whileidxself.n:ifvalself.tree[idx]:self.tree[idx]val idxidx-idxdefquery(self,idx):ans-1whileidx0:ifself.tree[idx]ans:ansself.tree[idx]idx-idx-idxreturnansdefsolve(data:str)-str:arrdata.strip().split()ifnotarr:returnnint(arr[0])Lint(arr[1])numslist(map(float,arr[2:2n]))# 对每个数取自然对数# 因为几何平均值最大 对数平均值最大logs[math.log(x)forxinnums]# 判断是否存在长度至少为 L 的子数组其平均 log 值 middefcan(mid:float)-bool:prefix[0.0]*(n1)foriinrange(1,n1):prefix[i]prefix[i-1]logs[i-1]-mid# 维护 prefix[0..i-L] 的最小值min_prefix0.0foriinrange(L,n1):ifprefix[i-L]min_prefix:min_prefixprefix[i-L]ifprefix[i]min_prefix-1e-15:returnTruereturnFalse# 二分最大平均值leftmin(logs)rightmax(logs)for_inrange(80):mid(leftright)/2.0ifcan(mid):leftmidelse:rightmid bestleft# 用 best 恢复最终区间prefix[0.0]*(n1)foriinrange(1,n1):prefix[i]prefix[i-1]logs[i-1]-best# 离散化前缀和方便树状数组使用sorted_valssorted(prefix)bitFenwickMax(len(sorted_vals)2)best_start0best_lenn1forjinrange(L,n1):# 把 j-L 这个前缀下标加入可选集合i_addj-L pos_addbisect.bisect_left(sorted_vals,prefix[i_add])1bit.update(pos_add,i_add)# 查询所有 prefix[j] 的前缀中最大的下标 i# i 越大区间 j-i 越短pos_querybisect.bisect_right(sorted_vals,prefix[j]1e-13)ibit.query(pos_query)ifi!-1:lengthj-iiflengthbest_lenor(lengthbest_lenandibest_start):best_lenlength best_startireturnf{best_start}{best_len}if__name____main__:print(solve(sys.stdin.read()))七、JavaScript算法源码// 读取标准输入constfsrequire(fs);constinputfs.readFileSync(0,utf8).trim().split(/\s/);letidx0;constNparseInt(input[idx],10);constLparseInt(input[idx],10);// 为了方便计算数组下标从 1 开始// a[i] 存储 ln(numbers[i])constanewArray(N1).fill(0);// 读入数据并取自然对数for(leti1;iN;i){constxparseFloat(input[idx]);a[i]Math.log(x);}// prefix[i] 表示前 i 个 ln 值的前缀和constprefixnewArray(N1).fill(0);for(leti1;iN;i){prefix[i]prefix[i-1]a[i];}// 双端队列存储候选左端点 jconstqnewArray(N1).fill(0);lethead0;lettail0;// 精度控制constEPS1e-12;// 计算区间 [j, i-1] 的对数平均值functionvalue(j,i){return(prefix[i]-prefix[j])/(i-j);}// 判断中间点 b 是否无用// 若 a、b、c 三个点中b 不可能成为最优左端点就将它弹出functionbad(aIdx,bIdx,cIdx){return(prefix[bIdx]-prefix[aIdx])*(cIdx-bIdx)(prefix[cIdx]-prefix[bIdx])*(bIdx-aIdx)-1e-18;}// 在当前右端点 i 下比较 j2 是否比 j1 更优functionbetter(j1,j2,i){returnvalue(j2,i)value(j1,i)EPS;}// 初始将前缀点 0 入队q[tail]0;// 最优答案letbestStart0;letbestLenL;letbestAvg-1e100;// i 表示前缀右端点对应原数组右边界为 i-1for(letiL;iN;i){// 新增一个可选左端点 k i - L// 因为子数组长度至少为 L所以左端点 j 必须满足 j i-Lconstki-L;// 维护凸包若队尾两个点和新点构成“中间点无用”则弹出队尾while(tail-head2bad(q[tail-2],q[tail-1],k)){tail--;}q[tail]k;// 查询最优左端点// 若队头下一个点比当前队头更优则弹出队头while(tail-head2better(q[head],q[head1],i)){head;}constjq[head];constcurAvgvalue(j,i);constcurStartj;// 原数组起点0-basedconstcurLeni-j;// 子数组长度// 更新答案// 1. 对数平均值更大// 2. 若相等长度更短// 3. 若长度也相等起点更靠前if(curAvgbestAvgEPS||(Math.abs(curAvg-bestAvg)EPS(curLenbestLen||(curLenbestLencurStartbestStart)))){bestAvgcurAvg;bestStartcurStart;bestLencurLen;}}// 按题意输出位置 大小console.log(bestStart bestLen);八、C算法源码#includestdio.h#includemath.h#defineMAXN100000#defineEPS1e-12// a[i] 存储 ln(numbers[i])doublea[MAXN5];// 前缀和数组doubleprefix[MAXN5];// 模拟队列存储候选左端点intq[MAXN5];/* * 计算区间 [j, i-1] 的对数平均值 * 即 (prefix[i] - prefix[j]) / (i - j) */doublevalue(intj,inti){return(prefix[i]-prefix[j])/(double)(i-j);}/* * 判断中间点 bIdx 是否无用 * 若无用则在维护凸包时应该将其删除 */intbad(intaIdx,intbIdx,intcIdx){return(prefix[bIdx]-prefix[aIdx])*(cIdx-bIdx)(prefix[cIdx]-prefix[bIdx])*(bIdx-aIdx)-1e-18;}/* * 在固定右端点 i 的情况下 * 判断 j2 是否比 j1 更优 */intbetter(intj1,intj2,inti){returnvalue(j2,i)value(j1,i)EPS;}intmain(){intN,L;if(scanf(%d %d,N,L)!2){return0;}// 读入数据并取自然对数for(inti1;iN;i){doublex;scanf(%lf,x);a[i]log(x);}// 计算前缀和prefix[0]0.0;for(inti1;iN;i){prefix[i]prefix[i-1]a[i];}inthead0,tail0;q[tail]0;// 初始前缀点 0 入队intbestStart0;intbestLenL;doublebestAvg-1e100;// 枚举右端点 ifor(intiL;iN;i){intki-L;// 维护凸包while(tail-head2bad(q[tail-2],q[tail-1],k)){tail--;}q[tail]k;// 查询最优左端点while(tail-head2better(q[head],q[head1],i)){head;}intjq[head];doublecurAvgvalue(j,i);intcurStartj;intcurLeni-j;// 更新答案if(curAvgbestAvgEPS||(fabs(curAvg-bestAvg)EPS(curLenbestLen||(curLenbestLencurStartbestStart)))){bestAvgcurAvg;bestStartcurStart;bestLencurLen;}}printf(%d %d\n,bestStart,bestLen);return0;}九、C算法源码#includebits/stdc.husingnamespacestd;staticconstintMAXN100000;staticconstdoubleEPS1e-12;// a[i] 存储 ln(numbers[i])doublea[MAXN5];// 前缀和数组doubleprefixSum[MAXN5];// 模拟队列保存候选左端点intq[MAXN5];/* * 计算区间 [j, i-1] 的对数平均值 */staticinlinedoublevalue(intj,inti){return(prefixSum[i]-prefixSum[j])/(double)(i-j);}/* * 判断点 bIdx 是否无用 * 若无用则在维护下凸壳时应该删除 */staticinlineboolbad(intaIdx,intbIdx,intcIdx){return(prefixSum[bIdx]-prefixSum[aIdx])*(cIdx-bIdx)(prefixSum[cIdx]-prefixSum[bIdx])*(bIdx-aIdx)-1e-18;}/* * 在固定右端点 i 时 * 判断 j2 是否比 j1 更优 */staticinlineboolbetter(intj1,intj2,inti){returnvalue(j2,i)value(j1,i)EPS;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,L;if(!(cinNL)){return0;}// 读入数据并取自然对数for(inti1;iN;i){doublex;cinx;a[i]log(x);}// 计算前缀和prefixSum[0]0.0;for(inti1;iN;i){prefixSum[i]prefixSum[i-1]a[i];}inthead0,tail0;q[tail]0;// 初始前缀点intbestStart0;intbestLenL;doublebestAvg-1e100;// 枚举右端点 ifor(intiL;iN;i){intki-L;// 维护凸包while(tail-head2bad(q[tail-2],q[tail-1],k)){--tail;}q[tail]k;// 查询最优左端点while(tail-head2better(q[head],q[head1],i)){head;}intjq[head];doublecurAvgvalue(j,i);intcurStartj;intcurLeni-j;// 更新答案if(curAvgbestAvgEPS||(fabs(curAvg-bestAvg)EPS(curLenbestLen||(curLenbestLencurStartbestStart)))){bestAvgcurAvg;bestStartcurStart;bestLencurLen;}}coutbestStart bestLen\n;return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。
华为OD机试 - 几何平均值最大子数组 - 二分查找(Python/JS/C/C++ 新系统 200分)
发布时间:2026/6/4 22:40:53
华为OD机试 新系统 统一考试题库清单持续收录中以及考点说明Python/JS/C/C。专栏导读本专栏收录于《华为OD机试真题Python/JS/C/C》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。一、题目描述从一个长度为N的正数数组numbers中找出长度至少为L且几何平均值最大的子数组并输出其位置和大小。K个数的几何平均值为K个数的乘积的K次方根若有多个子数组的几何平均值均为最大值则输出长度最小的子数组。若有多个长度相同的子数组的几何平均值均为最大值则输出最前面的子数组。二、输入描述第一行输入为N、L• N表示numbers的大小1 ≤ N ≤ 100000• L表示子数组的最小长度1 ≤ L ≤ N之后N行表示numbers中的N个数每个一行10-9≤ numbers[i] ≤ 109三、输出描述输出子数组的位置从0开始计数和大小中间用一个空格隔开。备注用例保证除几何平均值为最大值的子数组外其他子数组的几何平均值至少比最大值小10-10倍四、测试用例测试用例11、输入3 22232、输出1 23、说明候选子数组[2,2]几何平均值 2[2,3]几何平均值 √6[2,2,3]几何平均值 ∛12其中 [2,3] 最大所以输出起点 1长度 2。测试用例21、输入10 20.20.10.20.20.20.10.20.20.20.22、输出2 23、说明长度至少为 2 时最优是从下标 2 开始的 [0.2, 0.2]其几何平均值为 0.2。后面虽然也有很多 0.2,0.2但题目要求同值时取最前面的。五、解题思路1、为什么用二分查找“最大平均值子数组”是经典模型。假设我们二分一个答案 mid判断是否存在长度至少为 L 的子数组使得其平均值 mid。把每个元素变成c[i]b[i]−mid那么问题就变成是否存在长度至少为 L 的子数组其元素和 0。这个判断可以用前缀和在线性时间完成所以总复杂度就是二分约 80 次2、如何恢复最终区间二分出最大平均值后还要满足题目的额外规则几何平均值最大如果有多个取长度最小如果长度还相同取起点最靠前恢复区间时需要对每个右端点 j 找到i j-Lprefix[i] prefix[j]并且 i 尽可能大这样 j-i 最短这一步用前缀和离散化树状数组Fenwick Tree维护前缀范围内最大下标六、Python算法源码importsysimportmathimportbisect# 树状数组维护前缀范围内“最大的下标”classFenwickMax:def__init__(self,n):self.nn self.tree[-1]*(n2)defupdate(self,idx,val):whileidxself.n:ifvalself.tree[idx]:self.tree[idx]val idxidx-idxdefquery(self,idx):ans-1whileidx0:ifself.tree[idx]ans:ansself.tree[idx]idx-idx-idxreturnansdefsolve(data:str)-str:arrdata.strip().split()ifnotarr:returnnint(arr[0])Lint(arr[1])numslist(map(float,arr[2:2n]))# 对每个数取自然对数# 因为几何平均值最大 对数平均值最大logs[math.log(x)forxinnums]# 判断是否存在长度至少为 L 的子数组其平均 log 值 middefcan(mid:float)-bool:prefix[0.0]*(n1)foriinrange(1,n1):prefix[i]prefix[i-1]logs[i-1]-mid# 维护 prefix[0..i-L] 的最小值min_prefix0.0foriinrange(L,n1):ifprefix[i-L]min_prefix:min_prefixprefix[i-L]ifprefix[i]min_prefix-1e-15:returnTruereturnFalse# 二分最大平均值leftmin(logs)rightmax(logs)for_inrange(80):mid(leftright)/2.0ifcan(mid):leftmidelse:rightmid bestleft# 用 best 恢复最终区间prefix[0.0]*(n1)foriinrange(1,n1):prefix[i]prefix[i-1]logs[i-1]-best# 离散化前缀和方便树状数组使用sorted_valssorted(prefix)bitFenwickMax(len(sorted_vals)2)best_start0best_lenn1forjinrange(L,n1):# 把 j-L 这个前缀下标加入可选集合i_addj-L pos_addbisect.bisect_left(sorted_vals,prefix[i_add])1bit.update(pos_add,i_add)# 查询所有 prefix[j] 的前缀中最大的下标 i# i 越大区间 j-i 越短pos_querybisect.bisect_right(sorted_vals,prefix[j]1e-13)ibit.query(pos_query)ifi!-1:lengthj-iiflengthbest_lenor(lengthbest_lenandibest_start):best_lenlength best_startireturnf{best_start}{best_len}if__name____main__:print(solve(sys.stdin.read()))七、JavaScript算法源码// 读取标准输入constfsrequire(fs);constinputfs.readFileSync(0,utf8).trim().split(/\s/);letidx0;constNparseInt(input[idx],10);constLparseInt(input[idx],10);// 为了方便计算数组下标从 1 开始// a[i] 存储 ln(numbers[i])constanewArray(N1).fill(0);// 读入数据并取自然对数for(leti1;iN;i){constxparseFloat(input[idx]);a[i]Math.log(x);}// prefix[i] 表示前 i 个 ln 值的前缀和constprefixnewArray(N1).fill(0);for(leti1;iN;i){prefix[i]prefix[i-1]a[i];}// 双端队列存储候选左端点 jconstqnewArray(N1).fill(0);lethead0;lettail0;// 精度控制constEPS1e-12;// 计算区间 [j, i-1] 的对数平均值functionvalue(j,i){return(prefix[i]-prefix[j])/(i-j);}// 判断中间点 b 是否无用// 若 a、b、c 三个点中b 不可能成为最优左端点就将它弹出functionbad(aIdx,bIdx,cIdx){return(prefix[bIdx]-prefix[aIdx])*(cIdx-bIdx)(prefix[cIdx]-prefix[bIdx])*(bIdx-aIdx)-1e-18;}// 在当前右端点 i 下比较 j2 是否比 j1 更优functionbetter(j1,j2,i){returnvalue(j2,i)value(j1,i)EPS;}// 初始将前缀点 0 入队q[tail]0;// 最优答案letbestStart0;letbestLenL;letbestAvg-1e100;// i 表示前缀右端点对应原数组右边界为 i-1for(letiL;iN;i){// 新增一个可选左端点 k i - L// 因为子数组长度至少为 L所以左端点 j 必须满足 j i-Lconstki-L;// 维护凸包若队尾两个点和新点构成“中间点无用”则弹出队尾while(tail-head2bad(q[tail-2],q[tail-1],k)){tail--;}q[tail]k;// 查询最优左端点// 若队头下一个点比当前队头更优则弹出队头while(tail-head2better(q[head],q[head1],i)){head;}constjq[head];constcurAvgvalue(j,i);constcurStartj;// 原数组起点0-basedconstcurLeni-j;// 子数组长度// 更新答案// 1. 对数平均值更大// 2. 若相等长度更短// 3. 若长度也相等起点更靠前if(curAvgbestAvgEPS||(Math.abs(curAvg-bestAvg)EPS(curLenbestLen||(curLenbestLencurStartbestStart)))){bestAvgcurAvg;bestStartcurStart;bestLencurLen;}}// 按题意输出位置 大小console.log(bestStart bestLen);八、C算法源码#includestdio.h#includemath.h#defineMAXN100000#defineEPS1e-12// a[i] 存储 ln(numbers[i])doublea[MAXN5];// 前缀和数组doubleprefix[MAXN5];// 模拟队列存储候选左端点intq[MAXN5];/* * 计算区间 [j, i-1] 的对数平均值 * 即 (prefix[i] - prefix[j]) / (i - j) */doublevalue(intj,inti){return(prefix[i]-prefix[j])/(double)(i-j);}/* * 判断中间点 bIdx 是否无用 * 若无用则在维护凸包时应该将其删除 */intbad(intaIdx,intbIdx,intcIdx){return(prefix[bIdx]-prefix[aIdx])*(cIdx-bIdx)(prefix[cIdx]-prefix[bIdx])*(bIdx-aIdx)-1e-18;}/* * 在固定右端点 i 的情况下 * 判断 j2 是否比 j1 更优 */intbetter(intj1,intj2,inti){returnvalue(j2,i)value(j1,i)EPS;}intmain(){intN,L;if(scanf(%d %d,N,L)!2){return0;}// 读入数据并取自然对数for(inti1;iN;i){doublex;scanf(%lf,x);a[i]log(x);}// 计算前缀和prefix[0]0.0;for(inti1;iN;i){prefix[i]prefix[i-1]a[i];}inthead0,tail0;q[tail]0;// 初始前缀点 0 入队intbestStart0;intbestLenL;doublebestAvg-1e100;// 枚举右端点 ifor(intiL;iN;i){intki-L;// 维护凸包while(tail-head2bad(q[tail-2],q[tail-1],k)){tail--;}q[tail]k;// 查询最优左端点while(tail-head2better(q[head],q[head1],i)){head;}intjq[head];doublecurAvgvalue(j,i);intcurStartj;intcurLeni-j;// 更新答案if(curAvgbestAvgEPS||(fabs(curAvg-bestAvg)EPS(curLenbestLen||(curLenbestLencurStartbestStart)))){bestAvgcurAvg;bestStartcurStart;bestLencurLen;}}printf(%d %d\n,bestStart,bestLen);return0;}九、C算法源码#includebits/stdc.husingnamespacestd;staticconstintMAXN100000;staticconstdoubleEPS1e-12;// a[i] 存储 ln(numbers[i])doublea[MAXN5];// 前缀和数组doubleprefixSum[MAXN5];// 模拟队列保存候选左端点intq[MAXN5];/* * 计算区间 [j, i-1] 的对数平均值 */staticinlinedoublevalue(intj,inti){return(prefixSum[i]-prefixSum[j])/(double)(i-j);}/* * 判断点 bIdx 是否无用 * 若无用则在维护下凸壳时应该删除 */staticinlineboolbad(intaIdx,intbIdx,intcIdx){return(prefixSum[bIdx]-prefixSum[aIdx])*(cIdx-bIdx)(prefixSum[cIdx]-prefixSum[bIdx])*(bIdx-aIdx)-1e-18;}/* * 在固定右端点 i 时 * 判断 j2 是否比 j1 更优 */staticinlineboolbetter(intj1,intj2,inti){returnvalue(j2,i)value(j1,i)EPS;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intN,L;if(!(cinNL)){return0;}// 读入数据并取自然对数for(inti1;iN;i){doublex;cinx;a[i]log(x);}// 计算前缀和prefixSum[0]0.0;for(inti1;iN;i){prefixSum[i]prefixSum[i-1]a[i];}inthead0,tail0;q[tail]0;// 初始前缀点intbestStart0;intbestLenL;doublebestAvg-1e100;// 枚举右端点 ifor(intiL;iN;i){intki-L;// 维护凸包while(tail-head2bad(q[tail-2],q[tail-1],k)){--tail;}q[tail]k;// 查询最优左端点while(tail-head2better(q[head],q[head1],i)){head;}intjq[head];doublecurAvgvalue(j,i);intcurStartj;intcurLeni-j;// 更新答案if(curAvgbestAvgEPS||(fabs(curAvg-bestAvg)EPS(curLenbestLen||(curLenbestLencurStartbestStart)))){bestAvgcurAvg;bestStartcurStart;bestLencurLen;}}coutbestStart bestLen\n;return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。