题解 | #切割木头#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int cutWood(vector<int>& a, int k) {
        // 3个长度为m, m最大
        sort(a.begin(),a.end());
        int max_val = a.back();
        int left=1, right=max_val;
        // 看是否能取出来k个长度为m的木头
        while(left<=right) // 相当于查找右侧边界
        {
            int m=left+(right-left)/2;
            // 计算能取出来的木头段数
            int wood_num=0;
            for(int i:a) wood_num+=i/m;
            if(wood_num>=k)  left=m+1;// 取出的木头多于k, 说明长度太短, 搜索区间往右
            else if(wood_num<k)  right=m-1;
        }
        return left-1;
    }
};