Halve Array Sum (Max-Heap)
LeetCode 2208 用大根堆贪心：每次把当前最大值减半。
#resource / algorithm
#type / howto
#status / growing
#ds / heap
#algo / greedy
[!info] related notes 算法面试题型 MOC 堆常见题
Halve Array Sum (Max-Heap)
LeetCode: https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/
思路
要让总和尽快下降，贪心每次选择当前最大的数减半。
- 用大根堆维护当前数值。
- 目标是让累计减少量
reduced >= sum / 2。
Java Template
import java.util.*;
class Solution {
public int halveArray(int[] nums) {
PriorityQueue<Double> heap = new PriorityQueue<>(Collections.reverseOrder());
double sum = 0;
for (int v : nums) {
sum += v;
heap.add((double) v);
}
double target = sum / 2.0;
double reduced = 0;
int ops = 0;
while (reduced < target) {
double x = heap.poll();
double half = x / 2.0;
reduced += half;
heap.add(half);
ops++;
}
return ops;
}
}