题目描述#
给定一个整数数组 candies，其中 candies[i] 表示第 i 堆糖果的数量。你可以把每一堆糖果拆成任意数量的子堆，但不能将两堆重新合并。现在要给 k 个小孩分糖，要求每个小孩分到的糖果数量完全相同，且每个小孩至多拿走一堆。请问每个小孩最多能拿到多少糖果？
思路#
依旧是“二分答案”的典型场景：我们关心的是最大的可行糖果数 x。如果我们知道 x，就能线性遍历所有糖堆，计算总共可以拆出多少个大小为 x 的子堆；这一步是单调的——x 越小可行的子堆越多。因此可以把答案空间 [1, max(candies)] 进行二分。
二分上界#
- 如果所有糖果数量之和小于
k，说明再怎么拆也不够分，每个小孩得到0。 - 否则上界一定不超过最大糖堆，因为任何子堆都不会超过原始堆的大小。
二分答案check()检查#
check(candies, mid, k) 统计以 mid 为目标大小时可拆出的子堆数量：遍历每堆糖果，累计 c / mid，只要总和不少于 k 就说明可以让每个小孩拿到 mid 个糖果。
复杂度#
二分搜索的范围最多是 max(candies)，每次检查要扫描一遍数组，整体复杂度 O(n log max(candies))，额外空间为 O(1)。
代码#
class Solution {
public int maximumCandies(int[] candies, long k) {
long total = 0L;
int max = 0;
for (int c : candies) {
total += c;
max = Math.max(max, c);
}
if (total < k) {
return 0;
}
int left = 1, right = max;
while (left <= right) {
int mid = left + (right - left) / 2;
if (check(candies, mid, k)) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return right;
}
private boolean check(int[] candies, int target, long k) {
long count = 0L;
for (int c : candies) {
count += c / target;
if (count >= k) {
return true;
}
}
return false;
}
}