华为OD机试 - 魔法收积木 - 二进制（Java 新系统 200分）

华为OD机试 新系统 题库疯狂收录中刷题点这里专栏导读本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。一、题目描述公司要组织开展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)六、Java算法源码publicclassOdTest{/** * 计算一个正整数的二进制位数 * 例如 * 1 - 1 * 2(10) - 2 * 7(111) - 3 * 8(1000) - 4 * * 对于本题来说 * 一堆高度为 x 的积木若单独清空 * 每次魔法都相当于把 x 变成 x/2向下取整 * 直到变成 0。 * 这个过程的次数恰好等于 x 的二进制位数。 */privatestaticintbitLen(longx){return64-Long.numberOfLeadingZeros(x);}/** * 计算两个数在“不断除以2向下取整”这棵树中的最近公共祖先深度 * * 举例 * 4 的路径4 - 2 - 1 - 0 * 8 的路径8 - 4 - 2 - 1 - 0 * 它们最近公共祖先是 4深度bitLen(4)是 3 * * 这个深度的含义是 * 这两个相邻堆可以共享多少层“向下减半”的操作 * * 做法 * 1、先把位数更长的那个数不断右移直到两个数位数相同 * 2、如果此时还不相等则继续同时右移直到相等 * 3、相等时所在层的深度就是最近公共祖先深度 */privatestaticintlcaDepth(longa,longb){intlenAbitLen(a);intlenBbitLen(b);// 先把位数较长的数右移到和较短的数位数一致while(lenAlenB){a1;lenA--;}while(lenBlenA){b1;lenB--;}// 再同步右移直到两者相等while(a!b){a1;b1;lenA--;// 此时 lenA 和 lenB 始终相等只需同步减少一个即可}// 返回最近公共祖先所在深度returnlenA;}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);// 读取积木堆数量intnsc.nextInt();// 答案可能较大使用 longlongans0L;// 记录前一堆高度longprev0L;for(inti0;in;i){longcursc.nextLong();// 当前这一堆如果单独清空需要 bitLen(cur) 次魔法ansbitLen(cur);// 如果不是第一堆那么它和前一堆之间可以共享一部分操作// 共享的次数 两者最近公共祖先深度if(i0){ans-lcaDepth(prev,cur);}prevcur;}// 按题意只输出答案不输出任何提示文字System.out.print(ans);}}七、效果展示1、输入24 82、输出43、说明8 先变成 4然后两堆一起4 - 22 - 11 - 0总共 4 次下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 新系统 200分本专栏收录于《华为OD机试JAVA真题》。刷的越多抽中的概率越大私信哪吒备注华为OD加入华为OD刷题交流群每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景发现新题目随时更新全天CSDN在线答疑。