题目简介

给你一个正整数数组 nums 。每一次操作中，你可以从 nums 中选择 任意 一个数并将它减小到 恰好 一半。（注意，在后续操作中你可以对减半过的数继续执行操作）

请你返回将 nums 数组和 至少 减少一半的 最少 操作数。

提示：
1 <= nums.length <= 105
1 <= nums[i] <= 107

代码模板

class Solution {
public:
    int halveArray(vector<int>& nums) {
        
    }
};

简单分析

要求数组减半的次数，只需要求在数组恰好减半时，程序执行了多少次，并返回结果。如果要求的是最少次数的话，那就需要程序在执行每次操作的时候，尽可能减少比较大的数。要满足这个要求，我们可以在每次操作的时候减少数组中最大的数。

那要实现这个功能，我们可以这样操作：将输入的数据进行求和，并用两个变量来分别存储程序执行的次数以及【多次操作执行后减少的数据和】，将减少的数据和与原来的数据和进行比较，如果减少的数据和大于 或等于 原数据和的一半，那就应该停止对数据进行减半求和，并返回操作执行次数。

class Solution {
public:
    int halveArray(vector<int>& nums) {
        int m = nums.size();
        double n,j,d,k,q;
      
        //获取nums之和
        k = 0,j=0,n=0;
        k = accumulate(_nums.begin(), _nums.end(), 0.0);

        q = k / 2.0;
        for (int cptime=0;j<q;cptime++)
        {
            d = 0;
            //求最大值
            int max_number = 0;
            for (int ncptime = 1; ncptime <= m; ncptime++)
            {
                if (_nums[ncptime - 1] >= max_number)
                {
                    max_number = _nums[ncptime - 1];
                    d = ncptime - 1;
                }
                else
                {
                    continue;
                }
            }
            //减半，重新计数
            _nums[d] = _nums[d]/2.0;
            j += _nums[d];
            n = cptime+1;
        }
        return n;
    }
};

但这段代码是存在问题的，因为原数据是以 vector<int> 的数据类型进行存储的。所以当对其中的奇数如19进行减半后，结果9.5并不能存入数组内，而是会转化为整数后进行存储，这样会导致最后出现错误的结果。
因此，我们需要将原数组的数据类型进行转化后，再进行操作。修正后的代码如下：

class Solution {
public:
    int halveArray(vector<int>& nums) {
        int m = nums.size();
        double n,j,d,k,q;

        //转换数组
        vector<double> _nums;
        for (int i = 0; i < m; i++) {
            double converted = static_cast<double>(nums[i]);
            _nums.push_back(converted);
        }
        //获取nums之和
        k = 0,j=0,n=0;
        k = accumulate(_nums.begin(), _nums.end(), 0.0);

        q = k / 2.0;
        for (int cptime=0;j<q;cptime++)
        {
            d = 0;
            //求最大值
            int max_number = 0;
            for (int ncptime = 1; ncptime <= m; ncptime++)
            {
                if (_nums[ncptime - 1] >= max_number)
                {
                    max_number = _nums[ncptime - 1];
                    d = ncptime - 1;
                }
                else
                {
                    continue;
                }
            }
            //减半，重新计数
            _nums[d] = _nums[d]/2.0;
            j += _nums[d];
            n = cptime+1;
        }
        return n;
    }
};

使用STL库(优先队列)降低算法的时间复杂度

上方的代码虽然可以解决大部分问题，但算法的时间复杂度为$n^2$，如果处理大样本数据，效率可能会非常低下。实际上，上方代码也是无法完美通过leetcode的所有样本的（即大数据样本）。因此我们可以考虑改进算法以将其时间复杂度降低到$logn$。当然，我们可以在原代码上修改，但其实还有一个比较好的方法是使用优先队列。
在对最大值进行处理时，优先队列是一种比较适合的数据结构，优先队列是队列的一种，而队列也是c++中的一种STL库。合理使用STL库不仅可以减少代码量，而且还可以降低算法的时间复杂度，提高程序的运行效率。(当然，如果你认为效率还是不够，也可以自己设计一种更好的算法)
按照原来的思路改写代码，我们可以得到最终版本的代码：

class Solution {
public:
    int halveArray(vector<int>& nums) {
        double m,n,j;
        j = 0.0;
        int q;
        q = 0;
        //转换数组
        vector<double> _nums(nums.begin(), nums.end());
        //计算数组之和
        m = accumulate(_nums.begin(), _nums.end(), 0.0);
        n = m / 2;
        //创建优先队列
        priority_queue<double> k(_nums.begin(), _nums.end());
        //减半运算求值
        while (j < n && !k.empty())
        {
            double maxnumber = -1;
            maxnumber = k.top();
            k.pop();
            maxnumber /= 2.0;
            k.push(maxnumber);
            j += maxnumber;
            q++;
        }
        return q;
    }
};