目录
将数组和减半的最少操作数
除 2
将数组和减半的最少操作数
2208. 将数组和减半的最少操作次数 - 力扣（LeetCode）
https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/
由题意可知，我们可以遍历数组，把数组中的每个数都减半，来实现把数组和减半，但是这样的操作数不是最少的，为了使操作数最少，显然，我们可以每次找出数组中最大的数，把最大的数减半后，继续去找数组中最大的数。
我们可以利用大根堆来帮助我们找出数组中最大的数，把数组所有的数都放进大根堆之后，堆顶就是数组中最大的数，我们把堆顶减半后，删除堆顶元素，删除后会得到一个新的大根堆，此时我们再去取出大根堆的堆顶，就可以得到减半之后数组的最大数，再继续进行减半操作。
但删除的堆顶不是一去不复返了，按照题目要求，减半后的数可以再次进堆，继续执行操作。
以示例2为例，nums = [ 3 , 8 , 20 ]，堆顶为20，20减半之后为10，而 10 仍然是这个数组的最大数，我们可以继续对 10 进行减半操作。
class Solution {
public:int halveArray(vector<int>& nums) {double sum=0;priority_queue<double> heap;//大根堆for(auto& e:nums){sum+=e;heap.push(e);//入大根堆}sum/=2.0;//数组和的一半int count=0;//计数double t=0;while(sum>0){t=heap.top()/2.0;//将大根堆最大的数减半heap.pop();//删除堆顶，因为堆顶已经计算过了sum-=t;heap.push(t);//把减半后的数再次进大根堆count++;//次数+1}return count;}
};除 2
除2！ (nowcoder.com)https://ac.nowcoder.com/acm/problem/213140
和上一道题的思路类似，不过我们只能对偶数进行减半操作，故我们需要找出数组中最大的偶数，对偶数减半。
#include<iostream>
using namespace std;
#include<queue>
int main()
{long long int n,k;//cin>>n>>k;long long int num=0;long long int sum=0;priority_queue<long long int> heap;//大根堆while(n--){cin>>num;if(num%2==0)//偶数进堆heap.push(num);sum+=num;}while(k-- && heap.size())//堆为空 或者 可以操作的次数用完了，结束while循环{long long int t=heap.top();//堆顶t/=2;sum-=t;heap.pop();if(t%2==0)//减半后是偶数，进堆heap.push(t);}cout<<sum<<endl;return 0;
}
