「贪心算法」将数组和减半的最少操作次数

本文主要是介绍「贪心算法」将数组和减半的最少操作次数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

力扣原题链接，点击跳转。

给你一个数组，每次可以把其中一个数减半，可以对同一个数多次减半。至少操作多少次，才能让数组的和整体减少至少一半呢？

我们每次都选择当前数组中最大的那个数减半，就能减少最多，这就是贪心策略。可以创建一个大根堆，堆顶元素就是最大的那个数。每次取堆顶元素，减半后再入堆即可。

class Solution
{
public:int halveArray(vector<int>& nums){priority_queue<double> heap;double sum = 0.0;// 入堆并求和for (auto num : nums){sum += num;heap.push(num);}int cnt = 0;sum /= 2;while (sum > 0){// 一次减半double t = heap.top() / 2;sum -= t;cnt++;heap.pop();heap.push(t);}return cnt;}
};

这篇关于「贪心算法」将数组和减半的最少操作次数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---