LeetCode每日一题：完成所有工作的最短时间

传送门

思路

题目读完，很容易想到DFS的思路，很快就可以撸一个标准的dfs解法：

class Solution {
public:
    int ans = INT_MAX;
    int minimumTimeRequired(vector<int>& jobs, int k) {
        vector<int> works(k);
        const int n = jobs.size();
        dfs(0, works, jobs, 0, n, k);
        return ans;
    }

    void dfs(int now, vector<int>& w, vector<int>& j, int maxn, int n, int k) {
        if (maxn >= ans) return;
        if (now == n) {
            ans = maxn;
            return;
        }

        for (int i = 0; i < k; i++) {
            w[i] += j[now];
            dfs(now+1, w, j, max(maxn, w[i]), n, k);
            w[i] -= j[now];
        }
    }
};

记录当前最大值maxn，每次遍历到最后一个job就更新maxn到ans中。通过函数体中第一个if来维护“最小的最大值”。思路很清晰，可惜会超时。

根据题设，k和n的范围都是[1,12]，这个dfs的复杂度是O(kⁿ)的复杂度,也就是12¹²。这个值远大于1s内能处理的最大计算量(10⁷)，所以很遗憾，暴搜行不通。暴力来行不通的话，就来考虑优化吧

根据上述代码，可以看见剪枝就只有第一句if，如果我们当前记录的ans是一个“相当大”的值，那剪枝力度会变得很低。不幸的是，根据上面的代码，我们第一趟递归会将所有job全部分配给第0个工人，也就是说这时ans会记录一个很大的值，剪枝力度将会变得很小，自然也就容易超时了。

那么优化的思路也清晰了起来：尽可能的“平均”分配任务给所有工人，先优先保证每个工人手里都有活，再在有活的工人中进行枚举。

根据这个思路，得到以下代码，能超越88%的cpp代码。

代码

class Solution {
public:
    int ans = INT_MAX;
    int minimumTimeRequired(vector<int>& jobs, int k) {
        vector<int> works(k);
        const int n = jobs.size();
        dfs(0, 0, works, jobs, 0, n, k);
        return ans;
    }

    void dfs(int now, int past, vector<int>& w, vector<int>& j, int maxn, int n, int k) {
        // 当前最大值已经超过当前答案了
        // 一定无法达成"最小的最大"
        if (maxn >= ans) return;
        
        // 遍历结束，返回
        if (now == n) {
            ans = maxn;
            return;
        }

        // 优先给没被分配过工作的工人分配工作
        if (past < k) {
            w[past] += j[now];
            dfs(now + 1, past + 1, w, j, max(w[past], maxn), n, k);
            w[past] -= j[now];
        }

        // 常规遍历，注意这里的上界是我们记录的past值
        // 这样做是因为在上述过程中已经给每个工人都分了任务，
        // 接下来的操作就只用考虑这些手里有活的工人
        for (int i = 0; i < past; i++) {
            w[i] += j[now];
            dfs(now+1, past, w, j, max(maxn, w[i]), n, k);
            w[i] -= j[now];
        }
    }
};