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 have been given some number of products (possibly 0). Let x represent the maximum number of products given to any store. You want x 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
分配给商店的最多商品的最小值。
给你一个整数 n ，表示有 n 间零售商店。总共有 m 种产品，每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示，其中 quantities[i] 表示第 i 种商品的数目。你需要将 所有商品 分配到零售商店，并遵守这些规则：
- 一间商店 至多 只能有 一种商品 ，但一间商店拥有的商品数目可以为 任意 件。
- 分配后，每间商店都会被分配一定数目的商品（可能为 0 件）。用 x 表示所有商店中分配商品数目的最大值，你希望 x 越小越好。也就是说，你想 最小化 分配给任意商店商品数目的 最大值 。
请你返回最小的可能的 x 。
思路
思路是二分法，而且是有点类似875题那种在答案上二分的题目。题目是请我们把 m 种商品分配到 n 个商店里且需要尽量让每个商店分配商品数目的最大值越小越好。所以我们在做二分找 mid 的时候，mid 的意思是每个商店需要放多少件商品。如果按照 mid 的个数分配商品需要的商店个数 > n，则把 mid 改小；反之则把 mid 改大。
注意代码中 count 的计算方式，因为是计算需要的商店个数所以需要向上取整。
复杂度
时间O(nlogn)
空间O(1)
代码
Java实现
class Solution {
public int minimizedMaximum(int n, int[] quantities) {
int left = 1;
int right = 100000;
while (left < right) {
int mid = left + (right - left) / 2;
int count = 0;
for (int q : quantities) {
// count += (q + mid - 1) / mid;
count += q / mid;
if (q % mid != 0) {
count++;
}
}
if (count > n) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
}
相关题目
410. Split Array Largest Sum
774. Minimize Max Distance to Gas Station
875. Koko Eating Bananas
1011. Capacity To Ship Packages In N Days
1060. Missing Element in Sorted Array
1231. Divide Chocolate
1283. Find the Smallest Divisor Given a Threshold
1482. Minimum Number of Days to Make m Bouquets
1539. Kth Missing Positive Number
1870. Minimum Speed to Arrive on Time
2064. Minimized Maximum of Products Distributed to Any Store