华为OD机试 - 几何平均值最大子数组 - 二分查找（Java 新系统 200分）

华为OD机试 新系统 题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。一、题目描述从一个长度为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维护前缀范围内最大下标六、Java算法源码publicclassOdTest{/** * 由于输入规模可达 1e5这里自定义快速输入兼容整数/小数 */staticclassFastScanner{privatefinalInputStreaminSystem.in;privatefinalbyte[]buffernewbyte[116];privateintptr0,len0;privateintread()throwsIOException{if(ptrlen){lenin.read(buffer);ptr0;if(len0)return-1;}returnbuffer[ptr];}Stringnext()throwsIOException{StringBuildersbnewStringBuilder();intc;do{cread();}while(c!-1c );if(c-1)returnnull;while(c!-1c ){sb.append((char)c);cread();}returnsb.toString();}intnextInt()throwsIOException{returnInteger.parseInt(next());}doublenextDouble()throwsIOException{returnDouble.parseDouble(next());}}/** * 树状数组维护“某个前缀值范围内最大的下标” * 用于最终恢复答案时快速找到 * 在 i j-L 的前缀中满足 prefix[i] prefix[j] 的最大 i * 这样就能让区间长度 j-i 尽可能短 */staticclassFenwickMax{intn;int[]tree;FenwickMax(intn){this.nn;this.treenewint[n2];Arrays.fill(this.tree,-1);}voidupdate(intidx,intval){while(idxn){if(valtree[idx])tree[idx]val;idxidx-idx;}}intquery(intidx){intans-1;while(idx0){if(tree[idx]ans)anstree[idx];idx-idx-idx;}returnans;}}staticintN,L;staticdouble[]logs;/** * 判断是否存在长度至少为 L 的子数组 * 使得其 log 平均值 mid * * 等价于 * 对每个元素做变换 b[i] log(a[i]) - mid * 是否存在长度 L 的子数组其元素和 0 * * 时间复杂度 O(N) */staticbooleancan(doublemid){double[]prefixnewdouble[N1];for(inti1;iN;i){prefix[i]prefix[i-1](logs[i-1]-mid);}doubleminPrefix0.0;// 维护 prefix[0..i-L] 的最小值for(intiL;iN;i){minPrefixMath.min(minPrefix,prefix[i-L]);if(prefix[i]minPrefix-1e-15){returntrue;}}returnfalse;}/** * lowerBound在升序数组中找到第一个 target 的位置 */staticintlowerBound(double[]arr,doubletarget){intl0,rarr.length;while(lr){intm(lr)1;if(arr[m]target)rm;elselm1;}returnl;}/** * upperBound返回第一个 target 的位置 */staticintupperBound(double[]arr,doubletarget){intl0,rarr.length;while(lr){intm(lr)1;if(arr[m]target)rm;elselm1;}returnl;}/** * 利用已经二分出来的 best最大 log 平均值恢复真正答案。 * * 做法 * 1. 重新构造 transformed[i] log(a[i]) - best * 2. 若某个子数组的 transformed 和 0则说明它的平均值 best * 3. 因为二分精度足够高并且题目保证最优与非最优有间隔 * 所以这里筛出的就是最优子数组及其并列最优 * 4. 再按题意选 * - 几何平均值最大 * - 长度最小 * - 起点最靠前 * * 为了快速找“最短”的区间 * 对每个右端点 j找最大的 i且 i j-L满足 prefix[i] prefix[j] * 这样长度 j-i 最短。 * * 这个查询通过 * - 前缀和离散化 * - 树状数组维护前缀值范围内的最大下标 * 来实现复杂度 O(N log N) */staticint[]recover(doublebest){double[]prefixnewdouble[N1];for(inti1;iN;i){prefix[i]prefix[i-1](logs[i-1]-best);}// 离散化所有前缀和double[]sortedprefix.clone();Arrays.sort(sorted);FenwickMaxbitnewFenwickMax(sorted.length2);intbestStart0;intbestLenN1;for(intjL;jN;j){// 当前 j 能够配对的最新可加入前缀下标是 j-LintiToAddj-L;intposAddlowerBound(sorted,prefix[iToAdd])1;bit.update(posAdd,iToAdd);// 查询所有 prefix[j] 的前缀中最大的下标intposQueryupperBound(sorted,prefix[j]1e-13);intibit.query(posQuery);if(i!-1){intlenj-i;if(lenbestLen||(lenbestLenibestStart)){bestLenlen;bestStarti;}}}returnnewint[]{bestStart,bestLen};}publicstaticvoidmain(String[]args)throwsException{FastScannerfsnewFastScanner();Stringfirstfs.next();if(firstnull)return;NInteger.parseInt(first);Lfs.nextInt();logsnewdouble[N];doubleminLogDouble.POSITIVE_INFINITY;doublemaxLogDouble.NEGATIVE_INFINITY;for(inti0;iN;i){doublevalfs.nextDouble();logs[i]Math.log(val);minLogMath.min(minLog,logs[i]);maxLogMath.max(maxLog,logs[i]);}// 二分最大 log 平均值doubleleftminLog;doublerightmaxLog;// 迭代次数足够大保证误差远小于题目给出的区分精度for(intt0;t80;t){doublemid(leftright)/2.0;if(can(mid))leftmid;elserightmid;}int[]ansrecover(left);System.out.println(ans[0] ans[1]);}}七、效果展示1、输入5 1132212、输出1 13、说明因为 L1单个元素也可以作为子数组。最大几何平均值显然就是最大元素 3位置为 1长度为 1。下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。