2208. 將數組總和減半的最少操作次數

思路

題目的思路很好想，每次都選一個最大的數字x砍半，就能得到最少的操作次數。需要注意精度問題。
每次都要選最大值，並且會有新的數字x / 2加入，因此我們不能單純的排序數組，然後逐個取下去，
而是要考慮到新的數字x / 2。
使用heap能在 $O(\log{n})$ 的時間插入新資料，並保持有序性，因此用heap去取最大值。

優化的思路也很簡單，上個版本因為精度的關係，所以得用 double 類型。
現在我們將所有數字都統一移位，相當說每個數字有額外 20 次不會損失精度的操作（這個操作並不會影響答案）

A: 事物是相對的

並且用自己寫的heapify函數，跑得比較快。

程式碼

1. 優先隊列

class Solution {
public:
    int halveArray(vector<int>& nums) {
        double sum = 0;
        priority_queue<double> pq;
        for(int x : nums) {
            sum += x;
            pq.push((double)x);
        }
        double target = sum / 2.0;
        double removed = 0;
        int ops = 0;
        while(removed < target) {
            double x = pq.top(); pq.pop();
            double half = x / 2.0;
            removed += half;
            pq.push(half);
            ++ops;
        }
        return ops;
    }
};

2. 數值縮放 + 自寫 heapify

class Solution {
private:
    void heapify(vector<long long>& nums, int index) { // 向下調整
        int n = nums.size();
        int left = index * 2 + 1;
        while(left < n) {
            int best = left + 1 < n && nums[left + 1] > nums[left] ? left + 1 : left;
            best = nums[best] > nums[index] ? best : index;
            if(best == index) {
                break;
            }
            swap(nums[best], nums[index]);
            index = best;
            left = index * 2 + 1;
        }
    }
public:
    int halveArray(vector<int>& nums) {
        int n = nums.size();

        long long sum = 0;
        vector<long long> heap(n);
        for(int i = n - 1; i >= 0; --i){
            sum += (long long)nums[i] << 20;
            heap[i] = (long long)nums[i] << 20;
            heapify(heap, i); // 從下往上加入數字, 建立 heap
        }

        sum /= 2;
        int res = 0;
        for(long long cur = 0; cur < sum; ++res) {
            heap[0] /= 2;
            cur += heap[0];
            heapify(heap, 0);
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n\log{n})$，每次操作 heap 為 $O(\log n)$。
• 空間複雜度：$O(n)$。