求最小值的最大可能,使用二分法。
确定思路后最重要的是找到left,right分别是什么。
本题中因为题面明确说“分裂成两堆新的石子数量都大于等于1的石子堆”,故left初始值为1;
另,因为本题死分石子,故最小值的最大值为初始数组中的最小值,再分下去只能小于等于初始数组中的最小值,故right初始值为排序后的a[0];
计算过程为:
1)计算出mid;
2)根据mid计算当前石子可被分为sum堆(每堆与mid相除即为可分裂为几个);
3)sum与m比较,若sum>=m,说明mid值太小,将left改为mid;若sum<m,说明mid值太大,将right值改为mid - 1;
4)循环计算,直到right=left
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m long长整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, long long m, vector<int>& a) {
        // write code here
        sort(a.begin(), a.end());
        if (m == n) {
            return a[0];
        }
        
        int left = 1;
        int right = a[0];
        int mid = 0;
        while (left < right) {
            int sum = 0;
            if ((right + left) % 2 == 0) {
                mid = (right + left) / 2;
            } else {
                mid = (right + left + 1) / 2;
            }
            for (int i = 0; i < n; i++) {
                sum += (a[i] / mid);
            }
            if (sum >= m) {
                left = mid;
            } else {
                right = mid - 1;;
            }
        }
        
        return left;
    }
};