目录

将数组和减半的最少操作数

除 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;
}