题解 | #切割木头#

import java.util.*;

/**
 * NC382 切割木头
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型一维数组
     * @param k int整型
     * @return int整型
     */
    public int cutWood (ArrayList<Integer> a, int k) {
        return solution(a, k);
    }

    /**
     * 二分
     * @param a
     * @param k
     * @return
     */
    private int solution(ArrayList<Integer> a, int k){
        Collections.sort(a);

        int result = -1;
        int n = a.size();
        int left = 1;
        int right = a.get(n-1);
        int mid;
        while(left <= right){
            mid = left+(right-left)/2;
            if(checkCutWoods(a, k, mid)){
                result = mid;
                left = mid+1;
            }else{
                right = mid-1;
            }
        }

        return result;
    }

    /**
     * 校验截断后的木头是否满足条件(至少k个长度都为m的木头)
     * @param a
     * @param k
     * @param m
     * @return
     */
    private boolean checkCutWoods(ArrayList<Integer> a, int k, int m){
        int n = a.size();
        // 原始木头长度
        int val;
        // 截断后满足条件的木头数
        int cnt = 0;
        for(int i=n-1; i>=0; i--){
            val = a.get(i);
            if(val < m){
                break;
            }
            cnt += val/m;
            if(cnt >= k){
                return true;
            }
        }

        return false;
    }
}