5920. 分配給商店的最多商品的最小值

給你一個整數?n?，表示有?n?間零售商店。總共有?m?種產品，每種產品的數目用一個下標從 0?開始的整數數組?quantities?表示，其中?quantities[i]?表示第?i?種商品的數目。

你需要將 所有商品?分配到零售商店，并遵守這些規則：

一間商店 至多?只能有 一種商品 ，但一間商店擁有的商品數目可以為?任意?件。
分配后，每間商店都會被分配一定數目的商品（可能為 0?件）。用?x?表示所有商店中分配商品數目的最大值，你希望 x?越小越好。也就是說，你想 最小化?分配給任意商店商品數目的 最大值?。
請你返回最小的可能的?x?。

示例 1：輸入：n = 6, quantities = [11,6] 輸出：3 解釋： 一種最優方案為： - 11 件種類為 0 的商品被分配到前 4 間商店，分配數目分別為：2，3，3，3 。 - 6 件種類為 1 的商品被分配到另外 2 間商店，分配數目分別為：3，3 。 分配給所有商店的最大商品數目為 max(2, 3, 3, 3, 3, 3) = 3 。示例 2：輸入：n = 7, quantities = [15,10,10] 輸出：5 解釋：一種最優方案為： - 15 件種類為 0 的商品被分配到前 3 間商店，分配數目為：5，5，5 。 - 10 件種類為 1 的商品被分配到接下來 2 間商店，數目為：5，5 。 - 10 件種類為 2 的商品被分配到最后 2 間商店，數目為：5，5 。 分配給所有商店的最大商品數目為 max(5, 5, 5, 5, 5, 5, 5) = 5 。示例 3：輸入：n = 1, quantities = [100000] 輸出：100000 解釋：唯一一種最優方案為： - 所有 100000 件商品 0 都分配到唯一的商店中。 分配給所有商店的最大商品數目為 max(100000) = 100000 。

提示：

• m == quantities.length
• 1 <= m <= n <= $10^5$
• 1 <= quantities[i] <= $10^5$

解題思路

我們的目標最小化分配給任意商店商品數目的最大值，換句話說假設我們給某個商店最多分配商品的數量為k，而我們的目標就是要最小化這個k值，因此我們可知k值與能否將所有商品分配到商店是有單調性的

• 當k值增大的時候，我們可以給每家商店分配更多的同類商品，那么就必然可以將所有商品 分配到零售商店，例如n = 7, quantities = [15,10,10]，我們只要將k設置為15，那么我們只需要3家商店就可以將商品分配完
• 當k值減少時，我們需要更多的商店來接收商品，例如n = 7, quantities = [15,10,10]，我們將k設置為4的話，那么我們就需要10家商店才能將商品分配完。

因此，我們根據這種單調性，可以利用二分搜索，找出可以將商品分配完的最小的那個k值

代碼

class Solution { public:int minimizedMaximum(int n, vector<int>& quantities) {int m(0); for (auto c:quantities){m=max(c,m);}int l=1,r=m;while (l<=r){int mid=(r-l)/2+l;if (can_distribute(mid,quantities,n)){r=mid-1;}else l=mid+1;}return l;}bool can_distribute(int tar,vector<int>& quantities,int n){for (auto q:quantities){n-=(q%tar==0?q/tar:(q/tar)+1);}return n>=0;} };

總結

以上是生活随笔為你收集整理的5920. 分配给商店的最多商品的最小值的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。