【力扣每日一题】2023.7.25 将数组和减半的最少操作次数

目录

题目：

示例：

分析：

代码+运行结果：

---

题目：

示例：

分析：

题目给我们一个数组，我们每次可以将任意一个元素减半，问我们操作几次之后才可以将整个数组的和减半，这里的减半不是刚好减半，而是至少减去一半，所以我们多减一点是没关系的。

如果题目涉及到什么最大最小最多最少，那么我们大概率都是要用到贪心的思想。

既然要操作次数最小，那么我们每次把元素减半都应该尽量多减少一点，所以每次减少元素的一半，我们都应该把数组里最大的元素给减半。

那么我们就可以使用优先队列（大顶堆）来帮助我们维护数组的最大元素，然后每次把队列顶端（最大的数）拿出来，减半以后再放回去，并且把数组和对应的减去这个元素的一半。

如此循环操作直到数组和成功减半，我们返回次数即可。

代码+运行结果：

class Solution {
public:int halveArray(vector<int>& nums) {double SUM=0;priority_queue<double>pq;   //大顶堆(优先队列)for(const int &num:nums){   //统计总和并进入大顶堆SUM+=num;pq.push(num);}double target=SUM/2.0;  //获取总和的一半int res=0;while(SUM>target){  //不断循环直到SUM减半.res++;//获取栈顶(最大元素),把最大元素减半才能减少最多数double temp=pq.top();  pq.pop();temp/=2.0;SUM-=temp;  //总和减去该元素的一半pq.push(temp);  //减半后继续进入大顶堆}return res;}
};