魔法收积木
2025华为OD机试双机位C卷 - 华为OD上机考试双机位C卷 200分题型
华为OD机试双机位C卷真题目录点击查看: 华为OD机试双机位C卷真题题库目录｜机考题库 + 算法考点详解
题目描述
考友反馈题目大意:现在有n堆积木，每堆积木都有正整数数量，魔法一次可以把积木数量一致的积木堆砍半，要求出使用魔法收完积木堆的最少要用多少次魔法。
输入描述
第一行输入n代表积木的堆数
第二行输入：n个正整数，用空格分割，表示每堆积木的个数。
输出描述
输出使用魔法收完积木堆的最少要用多少次魔法。
用例1
输入
4 4 4 4 4输出
3用例2
输入
2 3 4输出
4题解
思路：贪心
魔法一次可以把积木数量一致的积木堆砍半，为了让使用魔法次数少，就是尽可能让一次魔法处理尽量多堆的积木。- 基于1，可以推导得到
先将最大的值砍半，尽可能让它和小的值一同进行处理。 - 这道题的基本逻辑就是：
1. 统计所有积木堆，使用哈希表存储不同大小积木堆的个数，
2. 每次将积木最多堆数量(x)砍半，使用魔法数量+1，更新哈希表mp[x/2] += mp[x]
3. 不断重复2的逻辑直到所有堆积木数量都变为0结束。 - 根据3的逻辑，主要是跟踪最大积木数量，对于java和C++都有对用的map使用，python、c++和go可以使用优先队列 + map去处理。
c++
#include<iostream> #include<vector> #include<string> #include <utility> #include <sstream> #include<algorithm> #include<cmath> #include<map> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; // 会自动按照key排序 记录不同数量积木数量 map<long, long> mp; for (int i = 0; i < n; i++) { long cnt; cin >> cnt; mp[cnt]++; } // 结果 long ans = 0; while (!mp.empty()) { auto it = prev(mp.end()); long x= it->first; long cnt = it->second; mp.erase(it); ans++; long nextX = x >> 1; if (nextX > 0) { mp[nextX] += cnt; } } cout << ans; return 0; }JAVA
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st; int n = Integer.parseInt(br.readLine().trim()); // TreeMap：有序 map，等价于 C++ map // key：积木数量，value：该数量出现的次数 TreeMap<Long, Long> mp = new TreeMap<>(); st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { long x = Long.parseLong(st.nextToken()); mp.put(x, mp.getOrDefault(x, 0L) + 1); } long ans = 0; while (!mp.isEmpty()) { // 取当前最大 key（等价于 prev(mp.end())） Map.Entry<Long, Long> entry = mp.lastEntry(); long x = entry.getKey(); long cnt = entry.getValue(); mp.pollLastEntry(); // 删除最大 key ans++; long nextX = x >> 1; if (nextX > 0) { mp.put(nextX, mp.getOrDefault(nextX, 0L) + cnt); } } System.out.println(ans); } }Python
importsysimportheapqfromcollectionsimportCounterdefmain():# 读取全部输入data=sys.stdin.read().strip().split()n=int(data[0])nums=list(map(int,data[1:1+n]))# 统计每种积木数量出现次数cnt=Counter(nums)# 用最大堆模拟取最大 key， python默认是最小堆，所以使用负数heap=[-xforxincnt.keys()]heapq.heapify(heap)ans=0whileheap:x=-heapq.heappop(heap)c=cnt.pop(x)ans+=1nx=x>>1ifnx>0:ifnxnotincnt:heapq.heappush(heap,-nx)cnt[nx]+=cprint(ans)if__name__=="__main__":main()JavaScript
'use strict';constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});letlines=[];rl.on('line',line=>{if(line.trim())lines.push(line.trim());});// 手写最大堆classMaxHeap{constructor(){this.data=[];}size(){returnthis.data.length;}// 插入元素push(val){this.data.push(val);this._siftUp(this.data.length-1);}// 弹出最大元素pop(){if(this.data.length===0)returnnull;consttop=this.data[0];constlast=this.data.pop();if(this.data.length>0){this.data[0]=last;this._siftDown(0);}returntop;}_siftUp(i){while(i>0){constp=Math.floor((i-1)/2);if(this.data[i]<=this.data[p])break;[this.data[i],this.data[p]]=[this.data[p],this.data[i]];i=p;}}_siftDown(i){constn=this.data.length;while(true){letmaxIdx=i;constl=2*i+1,r=2*i+2;if(l<n&&this.data[l]>this.data[maxIdx])maxIdx=l;if(r<n&&this.data[r]>this.data[maxIdx])maxIdx=r;if(maxIdx===i)break;[this.data[i],this.data[maxIdx]]=[this.data[maxIdx],this.data[i]];i=maxIdx;}}}rl.on('close',()=>{letidx=0;constn=Number(lines[idx++]);constnums=lines[idx].split(/s+/).map(Number);// Map: 记录每种积木数量出现的次数constmp=newMap();for(leti=0;i<n;i++){constx=nums[i];mp.set(x,(mp.get(x)||0)+1);}constheap=newMaxHeap();for(constkeyofmp.keys())heap.push(key);letans=0;while(heap.size()>0){// 最大数量个数letx=heap.pop();constcnt=mp.get(x);mp.delete(x);ans++;constnextX=x>>1;if(nextX>0){if(!mp.has(nextX))heap.push(nextX);mp.set(nextX,(mp.get(nextX)||0)+cnt);}}console.log(ans);});Go
packagemainimport("bufio""container/heap""fmt""os")// 最大堆（int64）typeMaxHeap[]int64func(h MaxHeap)Len()int{returnlen(h)}func(h MaxHeap)Less(i,jint)bool{returnh[i]>h[j]}// 大顶堆func(h MaxHeap)Swap(i,jint){h[i],h[j]=h[j],h[i]}func(h*MaxHeap)Push(xinterface{}){*h=append(*h,x.(int64))}func(h*MaxHeap)Pop()interface{}{old:=*h n:=len(old)x:=old[n-1]*h=old[:n-1]returnx}funcmain(){in:=bufio.NewReader(os.Stdin)varnintfmt.Fscan(in,&n)// 记录不同数量积木数量mp:=make(map[int64]int64)// 最大堆h:=&MaxHeap{}heap.Init(h)fori:=0;i<n;i++{varxint64fmt.Fscan(in,&x)ifmp[x]==0{heap.Push(h,x)}mp[x]++}// 结果varansint64=0forh.Len()>0{// 取最大x:=heap.Pop(h).(int64)ifmp[x]==0{continue}cnt:=mp[x]delete(mp,x)ans++nx:=x>>1ifnx>0{ifmp[nx]==0{heap.Push(h,nx)}mp[nx]+=cnt}}fmt.Println(ans)}