LC1760.袋子里最少数目的球

原题链接

思路：

• 二分查找解决最值问题
• 首先，转化成判断问题：给定maxOperations次，能不能使得所有袋子球的最大值不超过y个。
• 如果y变大了，那么需要的操作次数将会下降。二段性由此确定。袋子里面允许的最大值越多，需要的操作次数就越少。说明，存在一个最小的y，能够满足总次数<= maxOperations。（相当于找右区间的左端点）
• 对于“操作次数”数组而言，相当于取右半边数组的左侧端点。

• 假如一个袋子里面有x个球，拆分成若干个袋子，需要使得最大值<= y，需要操作的最少次数是多少？本质上就是一个向上取整的问题。

  • 

  • 

    代码：

    class Solution {
    public:
    bool check(int cost, vector<int>& nums, int maxOperations) {
       long long all_operations = 0;
       for (int num : nums) {
           all_operations += (num - 1) / cost; 
       }
       return all_operations <= (long long)(maxOperations);
    }
    int minimumSize(vector<int>& nums, int maxOperations) {
       // 假如我对开销没啥要求，再多都没事，那么maxOperations会变低
       // 逐步要求开销小，那么maxOperations慢慢上升，直到上升到题目要求的数字
       // 相当于取右半边数组的左端点。
       // left, right 代表的都是开销，即最少数量的球的个数
       int left = 1, right = 1e9 + 5;
       while (left < right) {
           int mid = (left + right) / 2;
           if (check(mid, nums, maxOperations)) {
               right = mid;
           } else {
               left = mid + 1;
           }
       }
       return left;
    }
    };