1760. 袋子里最少数目的球（二分查找算法）

 #### 审题 看到题目就想着用数学去怎么解决它，我们可以假设最小开销为X，那么我们只需要求解大于X的数拆解为均小于等于X的数最少需要几次即可。 #### 初审解答 很自然的可以想到**减一次X那么次数就减一**，直到这个数小于等于X，对数组里面的数据处理完后再去查看**次数是否大于等于0**，如果是那么说明这个X值可行，反之不可行。至于怎么去更快寻找这个X值呢，诶，用**二分查找**不就非常OK吗，到底可不可行呢？上代码看看 ```c++ class Solution { private: bool check(vector<int>& nums,int mid,int maxOperations){ int operations = 0; for(auto num:nums){ while(num>mid){ operations++; num-=mid; } } return operations<=maxOperations; } public: int minimumSize(vector<int>& nums, int maxOperations) { sort(nums.begin(),nums.end()); int left = 1; int right = nums[nums.size()-1]; int mid; while(left<=right){ mid = (left+right)/2; if(check(nums,mid,maxOperations)){ right=mid-1; }else{ left=mid+1; } } return left; } }; ``` 结果超时了，我们注意这个数据范围  #### 优化 是不是有点大，这个时候一个一个去减就太浪费时间了，有不有什么更快速的方法，那就是除法，这时候就需要注意了，如果这个数是9，X是3时，我们得到的结果是3，可是9只需要拆2次就可以了，我们可以将这个值num-1后再去除以X，那么就可以得到真实值了。代码如下 ```c++ class Solution { private: bool check(vector<int>& nums,int mid,int maxOperations){ int operations = 0; for(int &num:nums){ if(operations>maxOperations)break; operations+=(num-1)/mid; } return operations<=maxOperations; } public: int minimumSize(vector<int>& nums, int maxOperations) { sort(nums.begin(),nums.end()); int left = 1; int right = nums[nums.size()-1]; int mid; while(left<=right){ mid = (left+right)/2; if(check(nums,mid,maxOperations)){ right=mid-1; }else{ left=mid+1; } } return left; } }; ```  #### 完结撒花 哈哈，至此我们解决了今天的每日一题。 我的力扣主页：[https://leetcode.cn/u/nan-wan-bu-qiu-39/](https://leetcode.cn/u/nan-wan-bu-qiu-39/)