当前位置：首页 > news >正文

华为OD机试 - 魔法收积木 - 二进制（Python/JS/C/C++ 新系统 200分）

news 2026/6/6 17:49:39

华为OD机试新系统统一考试题库清单（持续收录中）以及考点说明（Python/JS/C/C++）。

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新。

一、题目描述

公司要组织开展Family Day活动，有一项游戏是堆积木比赛，现在比赛结束后，工作人员需要把积木收回仓库;现在工作人员面前有n堆
积木，第i推积木有Ni块相同大小的积木(单位高度: 1)组成，高度为hj。按正常情况，工作人员每次只能收取一块积木;

他觉得每次只能回收一块积木太慢了，决定使用魔法法术回收积木，且每次回收必须使用魔法。魔法可以对连续的堆相同高度的积木使
用，假设这一堆积木的高度为H，那么使用一次魔法可以把这一堆积木的高度都变为[H/2]，其中[H/2]表示对H/2向下取整。

工作人员想知道可以把所有积木都回收完成的最少魔法次数。

二、输入描述

第一行输入n ：代表积木的堆数

第二行输入 n个正整数，用空格分割，表示每堆积木的高度。

备注：

2 <=N <= 3*10^5
H <= hi
1< hi < 10^15

三、输出描述

一个整数表示答案; 输出使用魔法收完积木堆的最少要用多少次魔法。

四、测试用例

测试用例1：

1、输入

4
4 6 2 9

2、输出

3、说明

单独清空需要：3 + 3 + 2 + 4 = 12

相邻共享：

4 和 6 的公共祖先深度是 1
6 和 2 的公共祖先深度是 0
2 和 9 的公共祖先深度是 3

所以答案：12 - 1 - 0 - 3 = 8

测试用例2：

1、输入

4
4 4 4 4

2、输出

3、说明

四堆从一开始就全部相同且连续

可以始终一起操作：

4 -> 2
2 -> 1
1 -> 0

共 3 次

五、解题思路

每一堆积木高度为 hi，一次魔法只能对“连续且当前高度相同”的一段堆使用，并把它们同时变成 H/2。

如果只看单独一堆高度 hi：

hi -> hi/2 -> hi/4 -> … -> 0

每次都是右移一位

所以一堆单独清空所需次数，就是 hi 的二进制位数

例如：

4(100)：4 -> 2 -> 1 -> 0，共 3 次

9(1001)：9 -> 4 -> 2 -> 1 -> 0，共 4 次

也就是：

单堆代价 = bitLen(hi)

六、Python算法源码

importsysdefbit_len(x:int)->int:""" 计算正整数 x 的二进制位数 例如： 1 -> 1 2 -> 2 7 -> 3 8 -> 4 """returnx.bit_length()deflca_depth(a:int,b:int)->int:""" 计算 a 和 b 在“不断右移一位”这棵树中的最近公共祖先深度 做法： 1、先把位数更长的那个数右移到和另一个数位数相同 2、再同步右移，直到两个数相等 3、相等时的位数，就是最近公共祖先深度 """la=a.bit_length()lb=b.bit_length()# 先对齐位数whilela>lb:a>>=1la-=1whilelb>la:b>>=1lb-=1# 再同步右移直到相等whilea!=b:a>>=1b>>=1la-=1returnladefmain():data=list(map(int,sys.stdin.read().split()))ifnotdata:returnn=data[0]arr=data[1:1+n]ans=0prev=0fori,curinenumerate(arr):# 当前堆单独清空所需次数ans+=bit_len(cur)# 与前一堆的公共祖先深度，就是可共享的操作次数ifi>0:ans-=lca_depth(prev,cur)prev=cur# 按题意，直接输出答案print(ans,end="")if__name__=="__main__":main()

七、JavaScript算法源码

'use strict';constfs=require('fs');constinput=fs.readFileSync(0,'utf8').trim().split(/\s+/);if(input.length>0&&input[0]!==''){constn=Number(input[0]);constarr=[];// 题目中 hi < 1e15，超出 JS Number 的安全整数范围风险边缘// 为了绝对安全，这里使用 BigInt 处理for(leti=0;i<n;i++){arr.push(BigInt(input[i+1]));}functionbitLen(x){/** * 计算 BigInt 的二进制位数 * 直接转成二进制字符串，其长度就是位数 */returnx.toString(2).length;}functionlcaDepth(a,b){/** * 计算 a 和 b 的最近公共祖先深度 * 先对齐位数，再同步右移直到相等 */letla=bitLen(a);letlb=bitLen(b);while(la>lb){a>>=1n;la--;}while(lb>la){b>>=1n;lb--;}while(a!==b){a>>=1n;b>>=1n;la--;}returnla;}letans=0n;letprev=0n;for(leti=0;i<n;i++){constcur=arr[i];// 当前堆单独清空所需次数ans+=BigInt(bitLen(cur));// 减去和前一堆可共享的操作次数if(i>0){ans-=BigInt(lcaDepth(prev,cur));}prev=cur;}process.stdout.write(ans.toString());}

八、C算法源码

#include<stdio.h>typedefunsignedlonglongULL;/** * 计算正整数 x 的二进制位数 */intbit_len(ULL x){intlen=0;while(x>0){len++;x>>=1;}returnlen;}/** * 计算两个数在“不断除以2”这棵树中的最近公共祖先深度 * * 做法： * 1、先把位数较长的数右移到和较短的数位数一样 * 2、再同步右移直到相等 * 3、相等时所在层数，就是最近公共祖先深度 */intlca_depth(ULL a,ULL b){intla=bit_len(a);intlb=bit_len(b);while(la>lb){a>>=1;la--;}while(lb>la){b>>=1;lb--;}while(a!=b){a>>=1;b>>=1;la--;}returnla;}intmain(){intn;if(scanf("%d",&n)!=1){return0;}ULL ans=0;ULL prev=0;ULL cur;for(inti=0;i<n;i++){scanf("%llu",&cur);// 当前堆单独清空所需次数ans+=bit_len(cur);// 减去和前一堆可共享的操作次数if(i>0){ans-=lca_depth(prev,cur);}prev=cur;}printf("%llu",ans);return0;}

九、C++算法源码

#include<bits/stdc++.h>usingnamespacestd;usingull=unsignedlonglong;/** * 计算正整数 x 的二进制位数 */intbitLen(ull x){intlen=0;while(x>0){len++;x>>=1;}returnlen;}/** * 计算 a 和 b 的最近公共祖先深度 * * 先把位数更长的那个数右移到与另一个数位数相同， * 然后再同时右移，直到两者相等。 * 相等时的位数，就是最近公共祖先深度。 */intlcaDepth(ull a,ull b){intla=bitLen(a);intlb=bitLen(b);while(la>lb){a>>=1;la--;}while(lb>la){b>>=1;lb--;}while(a!=b){a>>=1;b>>=1;la--;}returnla;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cin>>n)){return0;}unsignedlonglongans=0;ull prev=0,cur;for(inti=0;i<n;i++){cin>>cur;// 当前堆单独清空所需次数ans+=bitLen(cur);// 减去与前一堆可以共享的操作次数if(i>0){ans-=lcaDepth(prev,cur);}prev=cur;}cout<<ans;return0;}