You are given an integer n
indicating there are n
specialty retail stores. There are m
product types of varying amounts, which are given as a 0-indexed integer array quantities
, where quantities[i]
represents the number of products of the ith
product type.
You need to distribute all products to the retail stores following these rules:
- A store can only be given at most one product type but can be given any amount of it.
- After distribution, each store will be given some number of products (possibly
0
). Letx
represent the maximum number of products given to any store. You wantx
to be as small as possible, i.e., you want to minimize the maximum number of products that are given to any store.
Return the minimum possible x
.
Example 1:
Input: n = 6, quantities = [11,6] Output: 3 Explanation: One optimal way is: - The 11 products of type 0 are distributed to the first four stores in these amounts: 2, 3, 3, 3 - The 6 products of type 1 are distributed to the other two stores in these amounts: 3, 3 The maximum number of products given to any store is max(2, 3, 3, 3, 3, 3) = 3.
Example 2:
Input: n = 7, quantities = [15,10,10] Output: 5 Explanation: One optimal way is: - The 15 products of type 0 are distributed to the first three stores in these amounts: 5, 5, 5 - The 10 products of type 1 are distributed to the next two stores in these amounts: 5, 5 - The 10 products of type 2 are distributed to the last two stores in these amounts: 5, 5 The maximum number of products given to any store is max(5, 5, 5, 5, 5, 5, 5) = 5.
Example 3:
Input: n = 1, quantities = [100000] Output: 100000 Explanation: The only optimal way is: - The 100000 products of type 0 are distributed to the only store. The maximum number of products given to any store is max(100000) = 100000.
Constraints:
m == quantities.length
1 <= m <= n <= 105
1 <= quantities[i] <= 105
Solution: Binary Search
Find the smallest max product s.t. all products can be distribute to <= n stores.
Time complexity: O(nlog(max(q)))
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua class Solution { public: int minimizedMaximum(int n, vector<int>& quantities) { int l = 1; int r = *max_element(begin(quantities), end(quantities)) + 1; while (l < r) { int cur = 0; int m = l + (r - l) / 2; for (int q : quantities) cur += (q + (m - 1)) / m; if (cur <= n) r = m; else l = m + 1; } return l; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment