网站正在建设中 文案,建设档案员证书查询网站,郑州企业建设网站服务,主机怎么装wordpress文章目录1. 题目2. 解题1. 题目
给你一个整数数组 nums #xff0c;其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。
你可以进行如下操作至多 maxOperations 次#xff1a;
选择任意一个袋子#xff0c;并将袋子里的球分到 2 个新的袋子中其中 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 10^5
1 maxOperations, nums[i] 10^9来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-limit-of-balls-in-a-bag 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
极小极大化 就用 二分查找
class Solution {
public:int minimumSize(vectorint nums, int maxOperations) {int l 1, r 1e9, mid, ans;while(l r){mid l((r-l)1);if(ok(nums, mid, maxOperations)){ans mid;r mid - 1;}elsel mid 1;}return ans;}bool ok(vectorint nums, int maxN, int maxOperations){int op 0;for(auto n : nums){op ceil(double(n)/maxN)-1;if(op maxOperations)return false;}return true;}
};168 ms 47.6 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
