C++ 解法, 执行用时: 3ms, 内存消耗: 436KB, 提交时间: 2022-05-21

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param m int整型 
     * @return int整型
     */
    int splitMin(vector<int>& num, int m) {
        int l = *max_element(num.begin(), num.end()), r = 1e9;

        auto ok = [&](int v) {
            int k = 1, now = 0;
            for (auto &i : num) {
                if (now + i > v) {
                    ++k;
                    now = i;
                } else {
                    now += i;
                }
                if (k > m) return false;
            }
            return true;
        };
        
        while (l < r) {
            int mid = l + r >> 1;
            if (ok(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

C++ 解法, 执行用时: 3ms, 内存消耗: 528KB, 提交时间: 2022-06-23

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param m int整型 
     * @return int整型
     */
    
    // 这一题和 NC408 第 K 小的距离对 技巧套路类似
    
    int splitMin(vector<int>& num, int m) {
        int l = *max_element(num.begin(), num.end()), r = 1e9;

        auto ok = [&](int v) {
            int k = 1, now = 0;
            for (auto &i : num) {
                if (now + i > v) {
                    ++k;
                    now = i;
                } else {
                    now += i;
                }
                if (k > m) return false;
            }
            return true;
        };
        
        while (l < r) {
            int mid = l + r >> 1;
            if (ok(mid)) r = mid;
            else l = mid + 1;
        }
        return r;
    }
};

C 解法, 执行用时: 4ms, 内存消耗: 408KB, 提交时间: 2022-06-27

int DFS(int* num, int n, int max_sum) {
    int z = 0;
    int y = max_sum;
    for (int i = 0; i < n; i++) {
        if (y >= num[i]) {
            y -= num[i];
        } else {
            z++;
            y = max_sum - num[i];
        }
    }
    z++;
    return z;
}
int splitMin(int* num, int n, int m) {
    int max_num = 0, sum_total = 0;
    for (int i = 0; i < n; i++) {
        if (num[i] > max_num) {
            max_num = num[i];
        }
        sum_total += num[i];
    }
    int a = max_num, b = sum_total, mid, c = sum_total + 1;
    while (a <= b) {
        mid = (a + b) / 2;
        if (DFS(num, n, mid) <= m) {
            c = mid;
            b = mid - 1;
        } else {
            a = mid + 1;
        }
    }
    return c;
}

C++ 解法, 执行用时: 4ms, 内存消耗: 416KB, 提交时间: 2022-06-27

class Solution {
  public:
    int splitMin(vector<int>& num, int m) {
        int a = *max_element(num.begin(), num.end()), c = 1e9;
        auto z = [&](int v) {
            int f = 1, k = 0;
            for (auto& i : num) {
                if (k + i > v) {
                    ++f;
                    k = i;
                } else {
                    k += i;
                }
                if (f > m) return false;
            }
            return true;
        };
        
        while (a < c) {
            int b = a + c >> 1;
            if (z(b)) c = b;
            else a = b + 1;
        }
        return c;
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-07-25

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param num int整型vector 
     * @param m int整型 
     * @return int整型
     */
    int splitMin(vector<int>& num, int m) {
    /* 题目要求将数组nums分割成n份，要求子数组累加和最大值尽可能小。
        反向思考：我们以threshold将nums中的元素进行分割，如果恰好分割成m份，说明threshold就是所求解；否则，若分割结果大于m，说明threshold取小了；否则，说明threshold取大了。
        threshold的取值范围：[max(nums), sum(nums)]
        对于threshold的选取，这里我们采用二分查找的方式*/
        int l=*max_element(num.begin(),num.end()),r=1e9;
        auto check=[&](int v){
            int k=1,now=0;
            for(auto& i:num){
                if(now+i<=v) now+=i;
                else{
                    now=i;
                    k++;
                }
                if(k>m) return false;
            }
            return true;
        };
        while(l<r){
            int mid=l+(r-l>>1);
            if(check(mid)) r=mid;
            else l=mid+1;
        }
        return l;
    }
};