题目描述

链接：https://www.nowcoder.com/questionTerminal/829419bde0e946b6b4fe813ed3972db8?answerType=1&f=discussion

题目中出现最小值最大、最大值最小的描述，一般都是需要二分答案(要求二分的答案具有单调性

以本题为例， 若最终答案为val，那么对于val - 1， val - 2,等等等，所有比val小的值都是可以满足题意的，所以本题答案具有单调性。

答案最小是0，最大时所有元素之和。此为二分的边界

二分的判定为，对于中值val 能否满足将数组分为k段且每段都大于等于val。

由于要求所取的元素是连续的，所以直接累加到>=val即可，统计当所有段的最小值为val时可以将数组分为多少段。 若分成段的个数大于等于k时即满足题意返回true，否则返回false；

public class Solution {
    /**
     * 分组
     * @param n int整型
     * @param k int整型
     * @param a int整型一维数组
     * @return int整型
     */
    public int solve (int n, int k, int[] a) {
        // write code here
        int sum = 0;
        for(int i = 0; i < a.length; i++){
            sum += a[i];
        }
        int l = 0, r = sum;
        while (l < r){
            int mid = (l + r + 1) / 2;
            if(check(k, a, mid)){
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    //最小值为val 分成k段是否够满足
    public static boolean check(int k, int[] a, int val){
        int countK = 0;
        int sum = 0;
        for(int i = 0; i < a.length; i++){
            sum += a[i];
            if(sum >= val){
                sum  = 0;
                countK++;
            }
        }
        return countK >= k;
    }
}