分组

• 假设数组a在k段切分方式下，每段的和为Si，即S1+S2+...+Sk=S(a)
• 又因为这个和是k个和里最小的，所以满足条件Smin<=S(a)/k
• 当想要Smin在所有切分方式中最大时，数组的切分会逐渐均匀（即每段和趋于一致），Smin会向S(a)/k逼近。
• 我们需要做的，就是依次尝试[0, S(a)/k]中的每一个值，看在数组尽量均匀被切分的情况下（即按顺序遍历数组，元素和达到这个值时就切断），能不能被切成K段。
• 如果能切分，说明我们还可以往更大的数试试。如果不能，就说明太大了，减小答案再试试。

import java.util.*;

public class Solution {
    public int solve (int n, int k, int[] a) {
        if(a.length == 0){
            return 0;
        }
        int sum = 0;
        for(int i = 0; i < n; i ++){
            sum  = sum + a[i];
        }
        if(k == 1){
            return sum;
        }
        int low = 0;
        int high = sum/k;
        while(low <= high){
            int mid = low + (high - low) / 2;
            if(check(a, k, mid)){
                low = mid + 1;
            }else{
                high = mid - 1;
            }
        }
        return (low+high)/2;
    }
    public boolean check(int a[], int k, int min_max_sum){
        int count = 0;
        int sum = 0;
        for(int j = 0; j < a.length; j++){
            sum += a[j];
            if(sum >= min_max_sum){
                sum = 0;
                count += 1;
                if(count >= k){
                    return true;
                }
            }
        }
        return false;
    }
}