魔法能量分配(C/Py/Java/Js/Go)题解华为笔试真题 7月1号 非AI方向第三题 300分题型题目内容在一个魔法世界中有nnn位法师和mmm个魔法水晶。每位法师都有一定的初始能量值每个水晶也蕴含着基础的魔法能量。法师可以通过吸收水晶来提升自己的能量但水晶的实际加成效果会受到法师初始能量的影响——法师初始能量越高水晶提供的能量加成越少。初始状态第iii位法师的初始能量值为a[i]a[i]a[i]第jjj个水晶的基础能量为b[j]b[j]b[j]。能量吸收规则当一个基础能量为b[j]b[j]b[j]的水晶被分配给初始能量值为a[i]a[i]a[i]的法师时并且这次分配是该法师个人吸收的第kkk个水晶(kkk从111开始计数)该法师实际增加的能量值为:b[j]−(k∗a[i])b[j] - (k * a[i])b[j]−(k∗a[i])。如果计算结果≤0\le 0≤0则该法师无法从此水晶获得任何能量自身能量也不会减少。使用限制每位法师可以吸收多个水晶也可以不吸收但每个水晶只能使用一次。目标合理分配所有水晶使分配后所有法师的能量之和达到最大。输入描述第一行两个整数nnn和mmm空格分隔表示nnn位法师mmm个魔法水晶。第二行空格分隔的nnn个整数表示每位法师的初始能量a[1],a[2],...,a[n]a[1],a[2],...,a[n]a[1],a[2],...,a[n]。第三行空格分隔的mmm个整数表示每个水晶的基础能量b[1],b[2],...,b[m]b[1],b[2],...,b[m]b[1],b[2],...,b[m]。输入约束1≤n≤1051 \le n \le 10^51≤n≤1051≤m≤1051 \le m \le 10^51≤m≤1051≤a[i]≤1051 \le a[i] \le 10^51≤a[i]≤1051≤b[j]≤1051 \le b[j] \le 10^51≤b[j]≤105输出描述一个整数表示分配水晶后所有法师增加的能量之和的最大值。样例1输入2 3 5 100 20 15 10输出20说明第一个水晶(魔法能量202020)分配给第一个法师(能量值555)增加能量为20−(1∗5)1520-(1*5)1520−(1∗5)15第二个水晶(魔法能量151515)应该分配给第一个法师增加的能量为15−(2∗5)515-(2*5)515−(2∗5)5合计202020第三个水晶分配后收益≤0\le0≤0不计入总和。题解思路思路:贪心收益b−代价,因此要想获得更大收益问题就变成了依次把水晶分配给当前可用的槽位每次都选择代价最小的槽位。同时为了让大的水晶产生更大的收益需要先处理能量最大的水晶再处理能量较小的水晶。所以根据1的分析代码处理策略就是水晶按能量从大到小排序用优先队列维护当前所有法师的最小可用槽位代价每次把当前最大的水晶分给当前代价最小的槽位。算法运行平均时间复杂度为O(mlogmmlognn)C#includebits/stdc.husingnamespacestd;intmain(){ios_base::sync_with_stdio(false);cin.tie(nullptr);intn,m;cinnm;vectorinta(n);vectorintb(m);for(inti0;in;i){cina[i];}for(inti0;im;i){cinb[i];}autocmp[](constpairint,inta,constpairint,intb){returna.first*a.secondb.first*b.second;};priority_queuepairint,int,vectorpairint,int,decltype(cmp)pq(cmp);// 初次将所有法师加入队列中for(inti0;in;i){pq.push({a[i],1});}longsum0;sort(b.begin(),b.end(),greaterint());for(inti0;im;i){pairint,intcurpq.top();pq.pop();intcostcur.first*cur.second;// 后续水晶能量更小槽位代价更大不会再有收益if(b[i]-cost0){break;}sumb[i]-cost;// 重新加入对应代价pq.push({cur.first,cur.second1});}coutsum;return0;}javaimportjava.util.*;publicclassMain{staticclassNode{intfirst;intsecond;Node(intfirst,intsecond){this.firstfirst;this.secondsecond;}}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);intnsc.nextInt();intmsc.nextInt();int[]anewint[n];Integer[]bnewInteger[m];for(inti0;in;i){a[i]sc.nextInt();}for(inti0;im;i){b[i]sc.nextInt();}PriorityQueueNodepqnewPriorityQueue((x,y)-Integer.compare(x.first*x.second,y.first*y.second));// 初次将所有法师加入队列中for(inti0;in;i){pq.offer(newNode(a[i],1));}longsum0;Arrays.sort(b,Collections.reverseOrder());for(inti0;im;i){Nodecurpq.poll();intcostcur.first*cur.second;// 后续水晶能量更小槽位代价更大不会再有收益if(b[i]-cost0){break;}sumb[i]-cost;// 重新加入对应代价pq.offer(newNode(cur.first,cur.second1));}System.out.print(sum);}}pythonimportheapqdefmain():n,mmap(int,input().split())alist(map(int,input().split()))blist(map(int,input().split()))pq[]# 初次将所有法师加入队列中forxina:heapq.heappush(pq,(x,1))sum_val0b.sort(reverseTrue)forenergyinb:first,secondheapq.heappop(pq)costfirst*second# 后续水晶能量更小槽位代价更大不会再有收益ifenergy-cost0:breaksum_valenergy-cost# 重新加入对应代价heapq.heappush(pq,(first,second1))print(sum_val,end)if__name____main__:main()javascriptconstreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin,output:process.stdout});letinput[];rl.on(line,line{input.push(line);});classPriorityQueue{constructor(compare){this.data[];this.comparecompare;}push(item){this.data.push(item);this.up(this.data.length-1);}pop(){consttopthis.data[0];constlastthis.data.pop();if(this.data.length){this.data[0]last;this.down(0);}returntop;}up(idx){while(idx0){letp(idx-1)1;if(!this.compare(this.data[idx],this.data[p]))break;[this.data[idx],this.data[p]][this.data[p],this.data[idx]];idxp;}}down(idx){constnthis.data.length;while(true){letsmallestidx;letlidx*21;letridx*22;if(lnthis.compare(this.data[l],this.data[smallest])){smallestl;}if(rnthis.compare(this.data[r],this.data[smallest])){smallestr;}if(smallestidx)break;[this.data[idx],this.data[smallest]][this.data[smallest],this.data[idx]];idxsmallest;}}}rl.on(close,(){const[n,m]input[0].split( ).map(Number);constainput[1].split( ).map(Number);constbinput[2].split( ).map(Number);constpqnewPriorityQueue((x,y)x[0]*x[1]y[0]*y[1]);// 初次将所有法师加入队列中for(leti0;in;i){pq.push([a[i],1]);}letsum0;b.sort((x,y)y-x);for(leti0;im;i){constcurpq.pop();constcostcur[0]*cur[1];// 后续水晶能量更小槽位代价更大不会再有收益if(b[i]-cost0){break;}sumb[i]-cost;// 重新加入对应代价pq.push([cur[0],cur[1]1]);}process.stdout.write(sum.toString());});Gopackagemainimport(bufiocontainer/heapfmtossort)typeNodestruct{firstintsecondint}typePriorityQueue[]Nodefunc(pq PriorityQueue)Len()int{returnlen(pq)}func(pq PriorityQueue)Less(i,jint)bool{returnpq[i].first*pq[i].secondpq[j].first*pq[j].second}func(pq PriorityQueue)Swap(i,jint){pq[i],pq[j]pq[j],pq[i]}func(pq*PriorityQueue)Push(xinterface{}){*pqappend(*pq,x.(Node))}func(pq*PriorityQueue)Pop()interface{}{old:*pq n:len(old)item:old[n-1]*pqold[:n-1]returnitem}funcmain(){in:bufio.NewReader(os.Stdin)varn,mintfmt.Fscan(in,n,m)a:make([]int,n)b:make([]int,m)fori:0;in;i{fmt.Fscan(in,a[i])}fori:0;im;i{fmt.Fscan(in,b[i])}pq:PriorityQueue{}heap.Init(pq)// 初次将所有法师加入队列中fori:0;in;i{heap.Push(pq,Node{a[i],1})}varsumint64sort.Slice(b,func(i,jint)bool{returnb[i]b[j]})fori:0;im;i{cur:heap.Pop(pq).(Node)cost:cur.first*cur.second// 后续水晶能量更小槽位代价更大不会再有收益ifb[i]-cost0{break}sumint64(b[i]-cost)// 重新加入对应代价heap.Push(pq,Node{cur.first,cur.second1})}fmt.Print(sum)}