1760. 袋子里最少数目的球
难度中等81
给你一个整数数组 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
提示：
- 1 <= nums.length <= 105
- 1 <= maxOperations, nums[i] <= 109
直接上正确答案，思路看注释，反正我第一次只想到了贪心和模拟，完全想不到二分法，看来以后要优先思考是不是二分的问题了。
class Solution {
public:
int minimumSize(vector& nums, int maxOperations) {
// 同样是 二分开销 初始的最小开销是1 最大开销是数组中的最大值
// 对于某一个开销 我们判断其是否可以达到的方法是：
// 求出每个袋子中的球数 对该开销的商的向上取整 再累加 判断是否大于maxOperations
// 区间 同样采用 左闭右闭 我们的目的是 找到第一个符合题意的开销
// 所以每次碰到一个符合条件的开销 我们就将右边界向左移动 以此来缩小查找区间
int left = 1, right = *max_element(nums.begin(), nums.end());
while (left < right) {
int mid = (right - left) / 2 + left;
int Operations = 0;
for (auto num : nums) {
Operations += num / mid; //将数组元素划分为不超过mid的值
//能够整除时：要减1，例如4/4=1，但是不需要分
if (num % mid == 0) Operations--;
}
//分的次数大于所给的:表示mid值太小，分的次数过多，需要减少分的次数
if (Operations > maxOperations) {
left = mid + 1;
}
else right = mid;
}
return left;
}
};
看到评论区的大佬，我真的是感觉路漫漫啊
学会了这道题，后面再刷一道：
875. 爱吃香蕉的珂珂
难度中等300收藏分享切换为英文接收动态反馈
珂珂喜欢吃香蕉。这里有 n 堆香蕉，第 i 堆中有 piles[i] 根香蕉。警卫已经离开了，将在 h 小时后回来。
珂珂可以决定她吃香蕉的速度 k （单位：根/小时）。每个小时，她将会选择一堆香蕉，从中吃掉 k 根。如果这堆香蕉少于 k 根，她将吃掉这堆的所有香蕉，然后这一小时内不会再吃更多的香蕉。
珂珂喜欢慢慢吃，但仍然想在警卫回来前吃掉所有的香蕉。
返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。
示例 1：
输入：piles = [3,6,7,11], h = 8 输出：4
示例 2：
输入：piles = [30,11,23,4,20], h = 5 输出：30
示例 3：
输入：piles = [30,11,23,4,20], h = 6 输出：23
提示：
- 1 <= piles.length <= 104
- piles.length <= h <= 109
- 1 <= piles[i] <= 109
通过次数70,374提交次数143,360
class Solution {
public:
int minEatingSpeed(vector& piles, int h) {
int left = 1, right = *max_element(piles.begin(), piles.end());
while (left < right) {
int mid = (right - left) / 2 + left;
int Operations = 0;
for (auto num : piles) {
Operations += num / mid+1; //将数组元素划分为不超过mid的值
//能够整除时：要减1，例如4/4=1，但是不需要分
if (num % mid == 0) Operations--;
}
//分的次数大于所给的:表示mid值太小，分的次数过多，需要减少分的次数
if (Operations > h) {
left = mid + 1;
}
else right = mid;
}
return left;
}
};
我就一下子就会了。
