1760. Minimum Limit of Balls in a Bag

You are given an integer array nums where the ith bag contains nums[i] balls. You are also given an integer maxOperations.

You can perform the following operation at most maxOperations times:

• Take any bag of balls and divide it into two new bags with a positive number of balls.

• For example, a bag of 5 balls can become two new bags of 1 and 4 balls, or two new bags of 2 and 3 balls.
  Your penalty is the maximum number of balls in a bag. You want to minimize your penalty after the operations.

Return the minimum possible penalty after performing the operations.

class Solution {
private:
    bool canDivide(vector<int>& nums, int op, long m) {
        int cnt = 0;
        for(auto it = upper_bound(nums.begin(), nums.end(), m); it != nums.end(); it++) {
            cnt += ceil(((double)*it / m) - 1);
        }

        return cnt <= op;
    }
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        long s = 1, e = INT_MAX, m, res = 0;
        sort(nums.begin(), nums.end());
        while(s <= e) {
            m = (e + s) / 2;
            if(canDivide(nums, maxOperations, m)) {
                res = m;
                e = m - 1;
            } else {
                s = m + 1;
            }
        }

        return res;
    }
};