二分查找、递归回溯， 剪枝优化，将数组分成k份，使最大的一份的和最小

力扣完成所有工作的最短时间

class Solution {
public:
    /* 
        @param idx 是jobs序号
     */
    bool recurse(int limit, int idx, vector<int> &jobs, vector<int> &workers) {
        if (idx == jobs.size()) {
            return true;
        }

        if (jobs[idx] > limit) {
            return false;
        }

        for (int w = 0; w < workers.size(); ++w) {
            if (workers[w] + jobs[idx] <= limit) {
                workers[w] += jobs[idx];

                if (recurse(limit, idx + 1, jobs, workers)) {
                    return true;
                }

                workers[w] -= jobs[idx];

                if (workers[w] == 0) {
                    //剪枝优化，当遇到前面的worker还没分配工作时，剪枝
                    break;
                }
            }
        }

        return false;
    }

    int minimumTimeRequired(vector<int>& jobs, int k) {
        sort(jobs.begin(), jobs.end(), greater<int>());

        int l = 0, r = accumulate(jobs.begin(), jobs.end(), 0);

        /* 使用二分法寻找符合的值，再去验证他 */
        while (l < r) {
            int mid = (l + r) / 2;
            vector<int> workers(k, 0);

            if (recurse(mid, 0, jobs, workers)) {
                r = mid;
            }
            else {
                l = mid + 1;
            }
        }

        return l;
    }
};