袋子里最少數(shù)目的球

給你一個整數(shù)數(shù)組nums，其中nums[i]表示第i個袋子里球的數(shù)目。同時給你一個整數(shù)maxOperations。

創(chuàng)新互聯(lián)建站網(wǎng)站建設(shè)由有經(jīng)驗的網(wǎng)站設(shè)計師、開發(fā)人員和項目經(jīng)理組成的專業(yè)建站團隊，負責(zé)網(wǎng)站視覺設(shè)計、用戶體驗優(yōu)化、交互設(shè)計和前端開發(fā)等方面的工作，以確保網(wǎng)站外觀精美、網(wǎng)站設(shè)計、網(wǎng)站建設(shè)易于使用并且具有良好的響應(yīng)性。

你可以進行如下操作至多maxOperations次：

選擇任意一個袋子，并將袋子里的球分到 2 個新的袋子中，每個袋子里都有 正整數(shù) 個球。
比方說，一個袋子里有 5 個球，你可以把它們分到兩個新袋子里，分別有 1 個和 4 個球，或者分別有 2 個和 3 個球。

你的開銷是單個袋子里球數(shù)目的 大值 ，你想要 最小化 開銷。

請你返回進行上述操作后的最小開銷。

示例 1

輸入：nums = [9], maxOperations = 2
輸出：3
解釋：
- 將裝有 9 個球的袋子分成裝有 6 個和 3 個球的袋子。[9] ->[6,3] 。
- 將裝有 6 個球的袋子分成裝有 3 個和 3 個球的袋子。[6,3] ->[3,3,3] 。
裝有最多球的袋子里裝有 3 個球，所以開銷為 3 并返回 3 。

示例 2

輸入：nums = [2,4,8,2], maxOperations = 4
輸出：2
解釋：
- 將裝有 8 個球的袋子分成裝有 4 個和 4 個球的袋子。[2,4,8,2] ->[2,4,4,4,2] 。
- 將裝有 4 個球的袋子分成裝有 2 個和 2 個球的袋子。[2,4,4,4,2] ->[2,2,2,4,4,2] 。
- 將裝有 4 個球的袋子分成裝有 2 個和 2 個球的袋子。[2,2,2,4,4,2] ->[2,2,2,2,2,4,2] 。
- 將裝有 4 個球的袋子分成裝有 2 個和 2 個球的袋子。[2,2,2,2,2,4,2] ->[2,2,2,2,2,2,2,2] 。
裝有最多球的袋子里裝有 2 個球，所以開銷為 2 并返回 2 。

示例 3

輸入：nums = [7,17], maxOperations = 2
輸出：7

提示

• 1<= nums.length<= 10⁵
• 1<= maxOperations, nums[i]<= 10⁹

算法一：二分查找 思路

• 首先給出一個定義：「給定花銷 mid ， 能否在 maxOperations 次操作內(nèi)使得盒子里所有的數(shù)都小于等于 mid」

• mid 越小，所需要的操作次數(shù)越多，因此就有了單調(diào)性，可以用二分查找來做。如果我們要將大值降低至 target ，可以計算一下需要多少操作數(shù)（每個數(shù)大于 target 的數(shù)都要盡可能均分），分為以下兩種情況：

  若操作數(shù)大于 maxOperations ，說明 target 太小了，需要往右搜索，否則需要往左搜索。

• 那么如何計算操作次數(shù) 呢？

  • 對于一個數(shù) x ，如果它小于等于 mid ， 那么不用劃分。

  • 如果大于 mid ，那么需要進行劃分。

    當(dāng) x 位于 [ mid + 1 ， mid * 2 ] ，需要劃分一次，位于 [ mid * 2 + 1 ，mid * 3] ，需要劃分兩次，因此可以看出需要劃分次數(shù)為 ： （x - 1） / mid 。

收獲

• 二分查找
  能否二分答案的關(guān)鍵在于問題是否具有決策單調(diào)性。也即考慮整個數(shù)軸，左邊一半滿足條件，右邊不滿足；或者左邊一半不滿足，右邊滿足。

  通過這道題復(fù)習(xí)了二分查找。

算法情況

• 時間復(fù)雜度 ：O（n log C）， 其中 n 是 nums 的長度，C 是數(shù)組 nums 中的大值， 不超過 10⁹。
• 空間復(fù)雜度：O（1）
  

代碼

class Solution {public:
    int minimumSize(vector& nums, int maxOperations) {int left = 1, right = *max_element(nums.begin(), nums.end());
        int res = 0;
        while(left<= right){int mid = (left + right) / 2;
            long long ops = 0;
            for(int num : nums){ops += (num - 1) / mid;
            }
            if(ops<= maxOperations){// 操作次數(shù)少，說明mid太大，減小mid
                res = mid;
                right = mid - 1;
            }
            else{// ops >maxOperations
                // mid太小，增大mid
                left = mid + 1;
            }
        }
        return res;
    }
};

參考資料

1. C++ max_element()的使用

max_element是用來來查詢大值所在的第一個位置。（不是下標(biāo)，比如 [1, 2 , 3 ]，會返回 3 ）

max_element有兩種寫法：

• 第一種是從頭迭代器到尾迭代器用自己寫的方法去比較，
• 第二種是直接用它自帶的頭迭代器到尾迭代器的比較大小。

2. 二分查找又死循環(huán)了？一個視頻講透二分本質(zhì)！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

當(dāng)前名稱：【LeetCode】1760.袋子里最少數(shù)目的球-創(chuàng)新互聯(lián)
URL網(wǎng)址：http://www.ekvhdxd.cn/article6/djoiig.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站建設(shè)、網(wǎng)站改版、網(wǎng)站設(shè)計公司、營銷型網(wǎng)站建設(shè)、App開發(fā)、響應(yīng)式網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)