前言

題目的鏈接，大家可以先試著去做一下再來看一下思路。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;}
};

策略證明

證明方法：交換認證法