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

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

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

你可以進(jìn)行如下操作至多maxOperations次：

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

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

請你返回進(jìn)行上述操作后的最小開銷。

示例 1

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

示例 2

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

示例 3

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

提示

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

算法一：二分查找 思路

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

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

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

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

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

  • 如果大于 mid ，那么需要進(jìn)行劃分。

    當(dāng) x 位于 [ mid + 1 ， mid * 2 ] ，需要?jiǎng)澐忠淮?，位?[ mid * 2 + 1 ，mid * 3] ，需要?jiǎng)澐謨纱?，因此可以看出需要?jiǎng)澐执螖?shù)為 ： （x - 1） / mid 。

收獲

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

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

算法情況

• 時(shí)間復(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是用來來查詢大值所在的第一個(gè)位置。（不是下標(biāo)，比如 [1, 2 , 3 ]，會(huì)返回 3 ）

max_element有兩種寫法：

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

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

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

文章題目：【LeetCode】1760.袋子里最少數(shù)目的球-創(chuàng)新互聯(lián)
文章源于：http://weahome.cn/article/djoiig.html