贪心算法-2208.将数组和减半的最小操作数-力扣(LeetCode)

一、题目解析

这里要注意恰好这个字眼，说明对任意数减小一半是不需要向上取整的，所以我们需要定义double类型的数据。

二、算法解析

我们需要将数组和减小为一半的次数最少，所以根据贪心算法，我们需要取数组中最大的数进行减半操作 ，但最优解也许不是每次都选择最大数进行减半操作，为什么贪心解就是正确的解呢？这个会在最后证明。

解法：贪心+大根堆

由于每次需要取最大的数进行 减半操作，我们可以使用大根堆来存储数据。

统计数组和的同时将数据插入到大根堆中，top出最大的数对其减半，然后pop掉原来数据，并将减半后的数重新插入回去，计数器++，然后重复这样的行为直到数组和减少到至少一半为止。

这里的大根堆使用 priority_queue容器。

根据上面的解析先自己编写代码，链接：2208. 将数组和减半的最少操作次数 – 力扣（LeetCode）

三、代码示例

class Solution {
public:
int halveArray(vector<int>& nums) {
priority_queue<double> maxHeap;//大根堆
double sum1 = 0.0;//sum1是原本的数组和
for(auto e : nums)
{
maxHeap.push(e);//插入元素
sum1 += e;
}
double sum2 = sum1;//sum2是减半后的数组和
int count = 0;
while((sum1 – sum2) < (sum1/2))//当减小的部分大于或等于sum1的一半时，循环结束
{
double tmp = maxHeap.top();//获取堆顶元素
maxHeap.pop();//删除堆顶元素
sum2 -= tmp;
sum2 += (tmp/2);
maxHeap.push(tmp/2);
count++;//计数器
}

return count;
}
};

 四、证明

证明方法：交换论证法

看到最后，如果对您有所帮助还请留下一个免费的赞和收藏，小编感激不尽，期待我们下期再见！