leetcode410分割数组的最大值（二分+贪心，困难）

class Solution {
public:
    int satisfy(vector<int> a, int n, int m);
    int splitArray(vector<int>& nums, int m) {
        //即找出一个整数，比它小的数字分组个数大于m，比它大的小于等于m,符合二分的思想，返回的是R
        //L初值取max(a)-1最好了，即不管分多少组都不满足， R初值取sum(nums) ,无论分成多少组每组都小于等于R,这样缩小的二分的范围，避免特殊考虑
        //数组划分中贪心的思想是比较常见的，即每个元素尽量往前面的组中放
        //vector中没有max, sum等函数
        int total = 0;
        for (int i = 0; i < nums.size(); i++){
            total += nums[i];
        }

        int max = nums[0];
        for (int i = 0; i < nums.size(); i++){
            if (nums[i] > max) max = nums[i];
        }

        int L = max - 1, R = total;
        while (L + 1 < R){
            int mid =  (R + L) / 2; //L + (R - L) / 2;
            if (satisfy(nums, mid, m)){  //m是组数，要传参过去！！
                R = mid;
            }else{
                L = mid;
            }
        }
        return R; 
    }
};
int Solution::satisfy(vector<int> a, int mid, int m){ 
    //把每个元素尽量往左边放，如果左边的和大于等于则放到新的组里面，贪心的思想
    //如果分成n组，则一定可以分成n+1组，n+2组等

    int group = 1;
    int group_sum = 0;
    for (int i = 0; i < a.size(); i++){
        group_sum += a[i];
        if (group_sum > mid){
            group++;
            group_sum = a[i]; //应该等于a[i] !!!而不是0
        }
    }
    return group <= m; 

  
}