文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一個(gè)正整數(shù)數(shù)組 nums 。每一次操作中，你可以從 nums 中選擇 任意 一個(gè)數(shù)并將它減小到 恰好 一半。（注意，在后續(xù)操作中你可以對(duì)減半過(guò)的數(shù)繼續(xù)執(zhí)行操作）

請(qǐng)你返回將 nums 數(shù)組和 至少 減少一半的 最少 操作數(shù)。

示例 1： 輸入：nums = [5,19,8,1] 輸出：3 解釋：初始 nums 的和為 5 + 19 + 8 + 1 = 33 。 以下是將數(shù)組和減少至少一半的一種方法： 選擇數(shù)字 19 并減小為 9.5 。 選擇數(shù)字 9.5 并減小為 4.75 。 選擇數(shù)字 8 并減小為 4 。 最終數(shù)組為 [5, 4.75, 4, 1] ，和為 5 + 4.75 + 4 + 1 = 14.75 。 nums 的和減小了 33 - 14.75 = 18.25 ，減小的部分超過(guò)了初始數(shù)組和的一半，18.25 >= 33/2 = 16.5 。 我們需要 3 個(gè)操作實(shí)現(xiàn)題目要求，所以返回 3 。 可以證明，無(wú)法通過(guò)少于 3 個(gè)操作使數(shù)組和減少至少一半。示例 2： 輸入：nums = [3,8,20] 輸出：3 解釋：初始 nums 的和為 3 + 8 + 20 = 31 。 以下是將數(shù)組和減少至少一半的一種方法： 選擇數(shù)字 20 并減小為 10 。 選擇數(shù)字 10 并減小為 5 。 選擇數(shù)字 3 并減小為 1.5 。 最終數(shù)組為 [1.5, 8, 5] ，和為 1.5 + 8 + 5 = 14.5 。 nums 的和減小了 31 - 14.5 = 16.5 ，減小的部分超過(guò)了初始數(shù)組和的一半， 16.5 >= 31/2 = 16.5 。 我們需要 3 個(gè)操作實(shí)現(xiàn)題目要求，所以返回 3 。 可以證明，無(wú)法通過(guò)少于 3 個(gè)操作使數(shù)組和減少至少一半。提示： 1 <= nums.length <= 10^5 1 <= nums[i] <= 10^7

來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/minimum-operations-to-halve-array-sum
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

• 貪心，優(yōu)先每次減去最大的數(shù)的一半，使用優(yōu)先隊(duì)列模擬即可

class Solution { public:int halveArray(vector<int>& nums) {double t = 0;priority_queue<double> q;for(auto& n : nums){t += n;q.push(n);}t /= 2.0;int ans = 0;while(t > 0.0){double n = q.top();q.pop();n /= 2.0;t -= n;ans++;q.push(n);}return ans;} };

208 ms 86.7 MB C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 2208. 将数组和减半的最少操作次数（优先队列）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。