Leetcode 410. 分割数组的最大值 (二分加贪心)

二分贪心，枚举这个最大值的最小值，注意是连续子数组，很好处理。

typedef long long LL;
class Solution {
public:
    int splitArray(vector<int>& nums, int m) {
        LL sum = 0, left = 0;
        for(int i=0;i<nums.size();i++) {
            if(nums[i]>left) left = nums[i];
            sum+=nums[i];
        }
        LL right = sum+1;
        while(left<=right){
            LL mid = (left+right)/2;
            if(judge(nums,m,mid)) right = mid-1;
            else left = mid + 1;
        }
        //cout<<left<<" "<<right<<endl;
        return left;
    }

    bool judge(vector<int>& nums, int m, LL k){
        LL sum = 0, count=1;
        for(int i=0;i<nums.size();i++){
            if(sum+nums[i]>k){
                count++;
                sum = 0;
            }
            if(sum+nums[i]<=k) sum+=nums[i];
        }
        return count<=m;
    }
};