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

华为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^5H hi1 hi 10^15三、输出描述一个整数表示答案; 输出使用魔法收完积木堆的最少要用多少次魔法。四、测试用例测试用例11、输入44 6 2 92、输出83、说明单独清空需要3 3 2 4 12相邻共享4 和 6 的公共祖先深度是 16 和 2 的公共祖先深度是 02 和 9 的公共祖先深度是 3所以答案12 - 1 - 0 - 3 8测试用例21、输入44 4 4 42、输出33、说明四堆从一开始就全部相同且连续可以始终一起操作4 - 22 - 11 - 0共 3 次五、解题思路每一堆积木高度为 hi一次魔法只能对“连续且当前高度相同”的一段堆使用并把它们同时变成 H/2。如果只看单独一堆高度 hihi - 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、相等时的位数就是最近公共祖先深度 laa.bit_length()lbb.bit_length()# 先对齐位数whilelalb:a1la-1whilelbla:b1lb-1# 再同步右移直到相等whilea!b:a1b1la-1returnladefmain():datalist(map(int,sys.stdin.read().split()))ifnotdata:returnndata[0]arrdata[1:1n]ans0prev0fori,curinenumerate(arr):# 当前堆单独清空所需次数ansbit_len(cur)# 与前一堆的公共祖先深度就是可共享的操作次数ifi0:ans-lca_depth(prev,cur)prevcur# 按题意直接输出答案print(ans,end)if__name____main__:main()七、JavaScript算法源码use strict;constfsrequire(fs);constinputfs.readFileSync(0,utf8).trim().split(/\s/);if(input.length0input[0]!){constnNumber(input[0]);constarr[];// 题目中 hi 1e15超出 JS Number 的安全整数范围风险边缘// 为了绝对安全这里使用 BigInt 处理for(leti0;in;i){arr.push(BigInt(input[i1]));}functionbitLen(x){/** * 计算 BigInt 的二进制位数 * 直接转成二进制字符串其长度就是位数 */returnx.toString(2).length;}functionlcaDepth(a,b){/** * 计算 a 和 b 的最近公共祖先深度 * 先对齐位数再同步右移直到相等 */letlabitLen(a);letlbbitLen(b);while(lalb){a1n;la--;}while(lbla){b1n;lb--;}while(a!b){a1n;b1n;la--;}returnla;}letans0n;letprev0n;for(leti0;in;i){constcurarr[i];// 当前堆单独清空所需次数ansBigInt(bitLen(cur));// 减去和前一堆可共享的操作次数if(i0){ans-BigInt(lcaDepth(prev,cur));}prevcur;}process.stdout.write(ans.toString());}八、C算法源码#includestdio.htypedefunsignedlonglongULL;/** * 计算正整数 x 的二进制位数 */intbit_len(ULL x){intlen0;while(x0){len;x1;}returnlen;}/** * 计算两个数在“不断除以2”这棵树中的最近公共祖先深度 * * 做法 * 1、先把位数较长的数右移到和较短的数位数一样 * 2、再同步右移直到相等 * 3、相等时所在层数就是最近公共祖先深度 */intlca_depth(ULL a,ULL b){intlabit_len(a);intlbbit_len(b);while(lalb){a1;la--;}while(lbla){b1;lb--;}while(a!b){a1;b1;la--;}returnla;}intmain(){intn;if(scanf(%d,n)!1){return0;}ULL ans0;ULL prev0;ULL cur;for(inti0;in;i){scanf(%llu,cur);// 当前堆单独清空所需次数ansbit_len(cur);// 减去和前一堆可共享的操作次数if(i0){ans-lca_depth(prev,cur);}prevcur;}printf(%llu,ans);return0;}九、C算法源码#includebits/stdc.husingnamespacestd;usingullunsignedlonglong;/** * 计算正整数 x 的二进制位数 */intbitLen(ull x){intlen0;while(x0){len;x1;}returnlen;}/** * 计算 a 和 b 的最近公共祖先深度 * * 先把位数更长的那个数右移到与另一个数位数相同 * 然后再同时右移直到两者相等。 * 相等时的位数就是最近公共祖先深度。 */intlcaDepth(ull a,ull b){intlabitLen(a);intlbbitLen(b);while(lalb){a1;la--;}while(lbla){b1;lb--;}while(a!b){a1;b1;la--;}returnla;}intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cinn)){return0;}unsignedlonglongans0;ull prev0,cur;for(inti0;in;i){cincur;// 当前堆单独清空所需次数ansbitLen(cur);// 减去与前一堆可以共享的操作次数if(i0){ans-lcaDepth(prev,cur);}prevcur;}coutans;return0;}下一篇华为OD机试真题 - 简易内存池Python/JS/C/C 新系统 200分本文收录于华为OD机试真题Python/JS/C/C刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新。