平台:LeetCode
题号:1760
给你一个整数数组 nums
,其中 nums[i]
表示第 i
个袋子里球的数目。同时给你一个整数 maxOperations
。
你可以进行如下操作至多 maxOperations
次:
2
个新的袋子中,每个袋子里都有 正整数 个球。5
个球,你可以把它们分到两个新袋子里,分别有 1
个和 4
个球,或者分别有 2
个和 3
个球。你的开销是单个袋子里球数目的 最大值 ,你想要 最小化 开销。请你返回进行上述操作后的最小开销。
示例 1:
输入:nums = [9], maxOperations = 2
输出:3
解释:
- 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
- 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
装有最多球的袋子里装有 3 个球,所以开销为 3 并返回 3 。
示例 2:
输入:nums = [2,4,8,2], maxOperations = 4
输出:2
解释:
- 将装有 8 个球的袋子分成装有 4 个和 4 个球的袋子。[2,4,8,2] -> [2,4,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,4,4,4,2] -> [2,2,2,4,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,4,4,2] -> [2,2,2,2,2,4,2] 。
- 将装有 4 个球的袋子分成装有 2 个和 2 个球的袋子。[2,2,2,2,2,4,2] -> [2,2,2,2,2,2,2,2] 。
装有最多球的袋子里装有 2 个球,所以开销为 2 并返回 2 。
示例 3:
输入:nums = [7,17], maxOperations = 2
输出:7
提示:
最小化不超过 max
次划分操作后的单个袋子最大值,我们将其称为「划分值」。
答案具有二段性:若使用
次划分操作后可达到最小划分值,此时减少划分操作次数,会使得划分值非单调上升。
因此我们可以二分答案,从而将问题进行等价转换:
**假设当前二分到的值为
,我们需要实现一个线性复杂度为 check
函数,判断能否使用不超过
次划分次数,来使得划分值不超过
**:
范围的划分值,均能使用不超过
次的实现,此时让
更小的划分值,则更无法在
次操作中满足,说明
范围划分值均不是答案,此时让
考虑如何实现 check
函数,从前往后处理每个
,根据
与当前限制
的大小关系进行分情况讨论:
:说明当前袋子不会成为瓶颈,无须消耗划分次数
:此时需要对当前袋子进行划分,直到满足单个袋子球的数量不超过
为止,由于每次划分相当于增加一个袋子,而将
划分成若干个不超过
个球的袋子,需要
个袋子,减去原本的一个,共需要增加
个新袋子,即划分
次
Java 代码:
class Solution {
public int minimumSize(int[] nums, int max) {
int l = 1, r = 0x3f3f3f3f;
while (l < r) {
int mid = l + r >> 1;
if (check(nums, mid, max)) r = mid;
else l = mid + 1;
}
return r;
}
boolean check(int[] nums, int limit, int max) {
int cnt = 0;
for (int x : nums) cnt += Math.ceil(x * 1.0 / limit) - 1;
return cnt <= max;
}
}
C++ 代码:
class Solution {
public:
int minimumSize(vector<int>& nums, int maxv) {
int l = 1, r = 0x3f3f3f3f;
while (l < r) {
int mid = l + r >> 1;
if (check(nums, mid, maxv)) r = mid;
else l = mid + 1;
}
return r;
}
bool check(vector<int>& nums, int limit, int maxv) {
int cnt = 0;
for (int x : nums) cnt += ceil(x * 1.0 / limit) - 1;
return cnt <= maxv;
}
};
Python 代码:
class Solution:
def minimumSize(self, nums: List[int], maxv: int) -> int:
def check(nums, limit, maxv):
return sum([(x + limit - 1) // limit - 1 for x in nums]) <= maxv
l, r = 1, 0x3f3f3f3f
while l < r:
mid = l + r >> 1
if check(nums, mid, maxv):
r = mid
else:
l = mid + 1
return r
TypeScript 代码:
function minimumSize(nums: number[], max: number): number {
function check(nums: number[], limit: number, max: number): boolean {
let cnt = 0
for (const x of nums) cnt += Math.ceil(x / limit) - 1
return cnt <= max
}
let l = 1, r = 0x3f3f3f3f
while (l < r) {
const mid = l + r >> 1
if (check(nums, mid, max)) r = mid
else l = mid + 1
}
return r
}
,其中
为值域大小