本文共 1591 字，大约阅读时间需要 5 分钟。

题目

给你一个整数数组 nums ，其中 nums[i] 表示第 i 个袋子里球的数目。同时给你一个整数 maxOperations 。

你可以进行如下操作至多 maxOperations 次：

• 选择任意一个袋子，并将袋子里的球分到 2 个新的袋子中，每个袋子里都有 正整数 个球。比方说，一个袋子里有 5 个球，你可以把它们分到两个新袋子里，分别有 1 个和 4 个球，或者分别有 2 个和 3 个球。
  你的开销是单个袋子里球数目的 最大值 ，你想要 最小化 开销。

请你返回进行上述操作后的最小开销。

示例一

输入：nums = [9], maxOperations = 2

• 将装有 9 个球的袋子分成装有 6 个和 3 个球的袋子。[9] -> [6,3] 。
• 将装有 6 个球的袋子分成装有 3 个和 3 个球的袋子。[6,3] -> [3,3,3] 。
  装有最多球的袋子里装有 3 个球，所以开销为 3 并返回 3 。

思路分析

这一类问题统称为最小值最大化或者最大值最小化。所谓的最小值最大化是指在所有满足条件的情况中选择最大的数值，而其满足的条件是使得某一数值可以最小化；所谓的最大值最小化是指在所有满足条件的情况中选择较小的数值，其满足的条件是使得一数值尽可能最大化。这种问题一般采用二分法进行搜索。

• 先找出所有可能性的范围，对于这道题来说，最终划分的球的代价最小是1，最大应该是这个数组里的最大值。
• 每次我们使用二分给定一个可能的数值mid,然后看是否能满足这个mid.过程应该是，对于数组中<mid的数字，其实我们是不需要划分的。对于>mid的数字，为了使其可以尽快收敛到mid，每次我们其实都是-mid的操作。
• 如果当前数字刚好可以整除mid，那么其需要分解的次数是num/mid-1；如果不能整除，那么其需要分解的次数是num/mid（下取整）。因此就可以归纳成(num-1)/mid

代码

class Solution {
   public:    int minimumSize(vector
   
    & nums, int maxOperations) {
           int r = 0, l = 1;        for(auto num : nums) r = max(r, num);        while(r > l){
               int mid = (l + r) >> 1;            int tot = 0;            for(auto num : nums){
                   if(num > mid){
                       // if(num % mid == 0) tot += num / mid - 1;                    // else tot += num / mid;                    // 上面针对奇偶的求次数的逻辑可以归结为                    tot += (num - 1) / mid;                }             }            if(tot <= maxOperations){
   //如果满足，边界移到mid                r = mid;            }else{
   //不满足，更新下边界                l = mid + 1;            }        }        return r;    }};
   

ps:对于二分查找，循环退出的条件，mid的更新，真滴是玄学。最好自己找张纸手算一下。

转载地址：https://blog.csdn.net/free1993/article/details/114279034 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！