白城做网站,c 可以做网站吗,天元建设集团有限公司济南中标项目,全国最新工商企业名录5920. 分配给商店的最多商品的最小值
给你一个整数 n #xff0c;表示有 n 间零售商店。总共有 m 种产品#xff0c;每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示#xff0c;其中 quantities[i] 表示第 i 种商品的数目。
你需要将 所有商品 分配到零售商…5920. 分配给商店的最多商品的最小值
给你一个整数 n 表示有 n 间零售商店。总共有 m 种产品每种产品的数目用一个下标从 0 开始的整数数组 quantities 表示其中 quantities[i] 表示第 i 种商品的数目。
你需要将 所有商品 分配到零售商店并遵守这些规则
一间商店 至多 只能有 一种商品 但一间商店拥有的商品数目可以为 任意 件。 分配后每间商店都会被分配一定数目的商品可能为 0 件。用 x 表示所有商店中分配商品数目的最大值你希望 x 越小越好。也就是说你想 最小化 分配给任意商店商品数目的 最大值 。 请你返回最小的可能的 x 。 示例 1输入n 6, quantities [11,6]
输出3
解释 一种最优方案为
- 11 件种类为 0 的商品被分配到前 4 间商店分配数目分别为2333 。
- 6 件种类为 1 的商品被分配到另外 2 间商店分配数目分别为33 。
分配给所有商店的最大商品数目为 max(2, 3, 3, 3, 3, 3) 3 。示例 2输入n 7, quantities [15,10,10]
输出5
解释一种最优方案为
- 15 件种类为 0 的商品被分配到前 3 间商店分配数目为555 。
- 10 件种类为 1 的商品被分配到接下来 2 间商店数目为55 。
- 10 件种类为 2 的商品被分配到最后 2 间商店数目为55 。
分配给所有商店的最大商品数目为 max(5, 5, 5, 5, 5, 5, 5) 5 。示例 3输入n 1, quantities [100000]
输出100000
解释唯一一种最优方案为
- 所有 100000 件商品 0 都分配到唯一的商店中。
分配给所有商店的最大商品数目为 max(100000) 100000 。提示
m quantities.length1 m n 10510^51051 quantities[i] 10510^5105
解题思路
我们的目标最小化分配给任意商店商品数目的最大值换句话说假设我们给某个商店最多分配商品的数量为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, vectorint quantities) {int m(0); for (auto c:quantities){mmax(c,m);}int l1,rm;while (lr){int mid(r-l)/2l;if (can_distribute(mid,quantities,n)){rmid-1;}else lmid1;}return l;}bool can_distribute(int tar,vectorint quantities,int n){for (auto q:quantities){n-(q%tar0?q/tar:(q/tar)1);}return n0;}
};
