leetcode 410 二分枚举 + 线性贪心检查是否能符合，时间复杂度O(nlog(sum))

class Solution {
public:
    bool canSplit(vector<int>& nums, int m, int mid){
        // cout << mid << ' ';
        long long sum = 0, cnt = 1;
        for(int &x: nums){
            if(sum + x > mid){
                sum = x;
                ++cnt;
                if(cnt > m) return false;
            }else sum += x;
        }
        return true;
    }
    int splitArray(vector<int>& nums, int m) {
        long long l = 0, r = 0;
        for(int &x: nums){
            r += x;
            if(x > l) l = x;
        }
        while(l < r){
            int mid = l + r >> 1;
            // cout << l << ' ' << r << ' ' << mid << endl;
            if(canSplit(nums, m, mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};