切割木头

import java.util.*;

public class Solution {
    /**
     *  二分法
     */
    public int cutWood (ArrayList<Integer> a, int k) {
        Collections.sort(a, Comparator.reverseOrder());
        int left = a.get(a.size() - 1), right = a.get(0);
        while (left < right) {
            int mid = left + (right - left + 1) / 2;
            if (canCut(a, mid, k)) {
                left = mid;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }
    
    private boolean canCut(ArrayList<Integer> a, int m, int k) {
        if (k == 0) return true;
        for (int i = 0; i < a.size() && a.get(i) >= m; i++) {
            int cur = a.get(i);
            if (cur >= m) {
                while (cur >= m) {
                    cur -= m;
                    k--;
                    if (k <= 0) return true;
                }
            } else {
                return false;
            }
        }
        return false;
    }
}