1760. Minimum Limit of Balls in a Bag

這題真的是鬼了, 我看了老半天猜不到是binary search, 不知道到底當場的人是怎麼想到的

簡單來說就是一個包包裡有球, 你可以將球分成兩包, 然後可以分最多k次, 希望在分k次後, 這些包包的裡最多球的包, 球數可以最小(相當於就是分得越平均越好)

假設, 我預計最小是mid個球

假設mid是3

A[i] = 2, 分成[2], 0 個Operation
A[i] = 3, 分成[3], 0 個Operation
A[i] = 4, 分成[3,1], 1個Operation
A[i] = 5, 分成[3,2], 1個Operation
A[i] = 6, 分成[3,3,], 1個Operation
A[i] = 7, 分成[3,3,1], 2個Operation
A[i] = 8, 分成[3,3,2], 2個Operation

所以我們的對一個球帶分裂的目標就是 a-1 / mid,

如果全部分割的總數太多, 代表mid太小了, 我們就會加大mid, left = mid + 1

反之, 就會降低, right = mid,

class Solution {
public:
    int minimumSize(vector<int>& nums, int maxOperations) {
        int size = nums.size();
        int l = 1;
        int r = 1e9;
        while(l < r){
            int mid = (l + r) /2;
            int sum = 0;
            for(auto a: nums){
                sum += (a - 1) / mid;
            }
          
            if(sum > maxOperations){
                l = mid + 1;
            }else{
                r = mid;
            }
        }
        return l;
        
    }
};

這真的超鬼的