【算法】贪心算法：将数组和减半的最少操作次数C++

前言

题目的链接，大家可以先试着去做一下再来看一下思路。2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）

题目解析

要认真去把题目看一遍，画出题目中的有用信息。

示例一定是最重要的部分，因为它可以帮助我们更好的去理解题目的意思，和后续我们对题目其他示例的挖掘。

算法原理

代码示例

class Solution {
public:int halveArray(vector<int>& nums) {priority_queue<double> heap;//题目中除2有些奇数是有小数的，所以我们选择double类型，优先队列。double sum = 0.0;//这个sum是统计所有数组中数的和for(auto x : nums)//将数组中的所有数入堆的同时累加到sum中{heap.push(x);sum += x;}sum = sum / 2.0;//这里除2后，sum就是数组中所有数一半的和，而题目要求就是将数组和减半的最少操作次数。所以只要sum<=0,即可实现。int count = 0;//用来记录执行的最少操作次数while(sum > 0){double t = heap.top() / 2.0;//取出堆顶元素并且除2heap.pop();//将堆顶元素出堆sum -= t;count++;heap.push(t);//再次将除2后的堆顶元素入堆}return count;}
};

策略证明

证明方法：交换认证法