一、环境说明

1. 本文是 LeetCode 1760题 : 袋子里最少数目的球，使用c语言实现
2. 思路转换题，使用二分查找。
3. 测试环境:Visual Studio 2019

二、代码展示

int minimumSize(int* nums, int numsSize, int maxOperations){
    int left = 1,right = 0,mid = 0;
    for(int i = 0;i<numsSize;i++){
        if(right<nums[i]){//找到所有桶中最大值
            right = nums[i];//最大值作为右边界
        }
    }
    while(left<=right){
        mid = left + ((right - left)>>1);//以mid为桶的最大值划分
        long long opt = 0;//需要的拆分次数
        for(int i = 0;i<numsSize;i++){
            opt += (nums[i] - 1)/mid;//等于下面三行
            //opt+=nums[i]/mid;//不能整除时,需要的拆分次数
            //if(0==nums[i]%mid)//能整除时，少拆分一次。
            //    opt--;
        }
        if(opt > maxOperations){//操作次数太多了，增加每个桶的最大值，以减少操作次数
            left = mid + 1;//左边界右移
        }else{
            right = mid -1;//右边界左移
        }
    }
    return left;//返回划分后，桶中最大值
}

三、思路分析

• 二分查找。
• 给定操作次数，求每个袋子最小的装球数。转换题意，求将每个袋子球数变成最少值，需要的opt次数。

1. 二分查找以mid为桶的最大值，进行操作。操作次数=每个桶的装球数/桶的最大值。注意，如果能整除，如9/3 = 3，实际只用划分2次，如果不能整除，如10/3=3，实际要划分3次，这个判定等价于(nums[i]-1)/mid。
2. opt+=(nums[i]-1)/mid，表示按照当前mid总共需要的opt的次数
3. 当操作数opt>maxOperations时，说明mid取值小了,让left = mid +1。
4. 最后我们找到的left就是刚好满足opt = maxOperations的最小桶数。

四、代码分析

• 理解思路很重要！
• 博主欢迎读者在评论区留言，作为日更博主，看到就会回复的。

五、AC

六、复杂度分析

1. 时间复杂度:O(nlog|C|) ,n是nums数组的大小，|C|是初始状态下，所有桶中的最大值。遍历nums，同时二分查找划分后桶最大值的时间复杂度是O(nlog|C|)
2. 空间复杂度:O(1),除了若干变量使用的常数空间，没有额外使用线性空间。