class Solution {
public:
int maximumCandies(vector<int>& candies, long long k) {
}
};
2226. 每个小孩最多能分到多少糖果
给你一个 下标从 0 开始 的整数数组 candies 。数组中的每个元素表示大小为 candies[i] 的一堆糖果。你可以将每堆糖果分成任意数量的 子堆 ，但 无法 再将两堆合并到一起。
另给你一个整数 k 。你需要将这些糖果分配给 k 个小孩，使每个小孩分到 相同 数量的糖果。每个小孩可以拿走 至多一堆 糖果，有些糖果可能会不被分配。
返回每个小孩可以拿走的 最大糖果数目 。
示例 1：
输入：candies = [5,8,6], k = 3 输出：5 解释：可以将 candies[1] 分成大小分别为 5 和 3 的两堆，然后把 candies[2] 分成大小分别为 5 和 1 的两堆。现在就有五堆大小分别为 5、5、3、5 和 1 的糖果。可以把 3 堆大小为 5 的糖果分给 3 个小孩。可以证明无法让每个小孩得到超过 5 颗糖果。
示例 2：
输入：candies = [2,5], k = 11 输出：0 解释：总共有 11 个小孩，但只有 7 颗糖果，但如果要分配糖果的话，必须保证每个小孩至少能得到 1 颗糖果。因此，最后每个小孩都没有得到糖果，答案是 0 。
提示：
1 <= candies.length <= 1051 <= candies[i] <= 1071 <= k <= 1012原站题解
python3 解法, 执行用时: 492 ms, 内存消耗: 27.9 MB, 提交时间: 2023-07-23 11:20:23
class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
# 判断每个小孩分到 i 个糖果时是否可以满足要求
def check(i: int) -> bool:
res = 0
for c in candies:
res += c // i
return res >= k
# 二分查找
l = 1
r = max(candies) + 1
while l < r:
mid = l + (r - l) // 2
if check(mid):
l = mid + 1
else:
r = mid
return l - 1
java 解法, 执行用时: 65 ms, 内存消耗: 56.7 MB, 提交时间: 2023-07-23 11:19:12
class Solution {
public int maximumCandies(int[] candies, long k) {
//确定查找区间
long sum = 0;
for (int val : candies) sum += val;
if (sum < k) return 0;
long left = 1, right = sum;
long ans = 0;
//二分答案进行查找
while (left <= right) {
long mid = left + (right - left) / 2;
if (check(candies, mid, k)) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return (int) ans;
}
//确定`check`方法
boolean check(int[] candies, long limit, long k) {
for (int val : candies) {
if (val < limit) continue;
else if (val == limit) k--;
else {
k -= val / limit;
}
}
return k <= 0;
}
}
cpp 解法, 执行用时: 128 ms, 内存消耗: 82.2 MB, 提交时间: 2023-07-23 11:18:24
class Solution {
public:
int maximumCandies(vector<int>& a, long long k) {
long long sum = 0;
for (int num : a)
sum += num;
/* low分得最少糖果数目，high分得最多糖果数目 */
long long low = 0, high = sum / k;
while (low != high) {
long long mid = (low + high + 1) / 2;// 二分糖果数目
long long heap = 0;// 按照每堆糖果数为mid的糖果一共可以分多少堆
/* 更新堆的个数 */
for (int num : a)
heap += num / mid;
/* 判断按当前糖果数分的对数和孩子个数进行判断 */
if (heap < k)
high = mid - 1;
else
low = mid;
}
return (int)high;
}
};
java 解法, 执行用时: 24 ms, 内存消耗: 57 MB, 提交时间: 2023-07-23 11:17:42
class Solution {
public int maximumCandies(int[] candies, long k) {
// 二分法
int max = candies[0];
for(int candy : candies) max = Math.max(max, candy);
// 每个孩子最多能分max个糖果
int left = 0, right = max;
while(left < right) {
// 右边主动收缩应该主动偏右
int mid = left + (right - left + 1) / 2;
if(getKids(candies, mid) < k) {
// 减治法:不行的先排除
// 不够分这么多孩子,每个孩子分少点->向左查找
right = mid - 1;
} else {
// 可能刚好够分或者多了->向右查找
left = mid;
}
}
return left;
}
// 当每个孩子分candiesNum颗糖果时最多能分多少个孩子
private long getKids(int[] candies, int candiesNum) {
long count = 0;
for(int candy : candies) {
count += candy / candiesNum;
}
return count;
}
}
python3 解法, 执行用时: 472 ms, 内存消耗: 28.1 MB, 提交时间: 2023-07-23 11:15:50
class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
if k > sum(candies): return 0
r = max(candies)
l = 1
while l <= r:
mid = (l + r) >> 1 # 二分
cnt = 0
for x in candies:
cnt += x // mid
if cnt >= k:
l = mid + 1
else:
r = mid - 1
return r
golang 解法, 执行用时: 168 ms, 内存消耗: 9.4 MB, 提交时间: 2023-07-23 11:13:39
func maximumCandies(candies []int, k int64) int {
return sort.Search(1e7, func(size int) bool {
size++
cnt := int64(0)
for _, candy := range candies {
cnt += int64(candy / size)
}
return cnt < k
})
}
python3 解法, 执行用时: 304 ms, 内存消耗: 28.1 MB, 提交时间: 2023-07-23 11:12:57
class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
# 由于 x 越大 sum 越小，而 key 需要一个增函数（非减），因此对 sum 取相反数从而满足要求
return bisect_right(range(sum(candies) // k), -k, key=lambda x: -sum(v // (x + 1) for v in candies))