1199. 建造街区的最短时间

你是个城市规划工作者，手里负责管辖一系列的街区。在这个街区列表中 blocks[i] = t 意味着第 i 个街区需要 t 个单位的时间来建造。

由于一个街区只能由一个工人来完成建造。

所以，一个工人要么需要再召唤一个工人（工人数增加 1）；要么建造完一个街区后回家。这两个决定都需要花费一定的时间。

一个工人再召唤一个工人所花费的时间由整数 split 给出。

注意：如果两个工人同时召唤别的工人，那么他们的行为是并行的，所以时间花费仍然是 split。

最开始的时候只有 一个 工人，请你最后输出建造完所有街区所需要的最少时间。

示例 1：

输入：blocks = [1], split = 1
输出：1
解释：我们使用 1 个工人在 1 个时间单位内来建完 1 个街区。

示例 2：

输入：blocks = [1,2], split = 5
输出：7
解释：我们用 5 个时间单位将这个工人分裂为 2 个工人，然后指派每个工人分别去建造街区，从而时间花费为 5 + max(1, 2) = 7

示例 3：

输入：blocks = [1,2,3], split = 1
输出：4
解释：
将 1 个工人分裂为 2 个工人，然后指派第一个工人去建造最后一个街区，并将第二个工人分裂为 2 个工人。
然后，用这两个未分派的工人分别去建造前两个街区。
时间花费为 1 + max(3, 1 + max(1, 2)) = 4

提示：

1. 1 <= blocks.length <= 1000
2. 1 <= blocks[i] <= 10^5
3. 1 <= split <= 100

动态规划-函数递归+备忘录

一般的动态规划都是i依赖于i-1，本题中i依赖于2*i和i-1。

两种状态，

• 一种是没人干活，所有人都分裂，
• 一种是有人干活，剩下的人分裂，有人干活可以递归到只有一个人干活。

class Solution {
    public int minBuildTime(int[] blocks, int split) {
        // 将 blocks 数组排序，以便从最小到最大的顺序处理
        Arrays.sort(blocks);
        
        int length = blocks.length;
        // 创建 memo 数组，用于存储中间结果，避免重复计算
        int[][] memo = new int[length][length];
        
        // 从最后一个元素开始，递归计算最小构建时间
        int ans = recursion(blocks, split, 1, length - 1, memo);
        return ans;
    }

    // 工人数量可能递增也可能递减，街区数量一定递减
    static int recursion(int[] blocks, int split, int numOfWorkers, int index, int[][] memo) {
        // 如果工人的数量大于等于需要处理的块数，直接返回当前块的时间
        // 工人数量递增结束的条件
        if (numOfWorkers >= index + 1) {
            return blocks[index];
        }
        // 如果当前状态已经计算过，直接返回结果
        if (memo[numOfWorkers][index] > 0) {
            return memo[numOfWorkers][index];
        }

        // 没人干活，计算所有工人同时分裂的时间。
        int allCall = split + recursion(blocks, split, numOfWorkers * 2, index, memo);
        // 如果只有一个工人，返回所有工人同时分裂的时间
        // 工人数量递减结束的条件
        if (numOfWorkers == 1) {
            return allCall;
        }
        // 有人干活，计算一个工人处理当前块，剩余工人处理剩余块的时间的最大值
        int oneDo = Math.max(blocks[index], recursion(blocks, split, numOfWorkers - 1, index - 1, memo));

        // 选择两种方案中较小的时间
        int ans = Math.min(allCall, oneDo);
        // 记录当前状态的结果，避免重复计算
        memo[numOfWorkers][index] = ans;
        return ans;
    }
}

• 时间复杂度：$O(2^n)$。
• 空间复杂度：$O(n^2)$。

Huffman Tree-主客易位

我们不妨换一个角度来理解，如果我们不是分裂工人，而是合并街区呢? 上面两个街区的情形中，分裂工人的操作，实际上就等价于把这两个街区合并为了一个建造时间为 split+max(blocks[0], blocks[1]) 的新街区。 这个问题类似多人过河问题。

class Solution {
    public int minBuildTime(int[] blocks, int split) {
        // 创建一个优先队列（最小堆）
        Queue<Integer> pq = new PriorityQueue<>();

        // 将所有的块添加到优先队列中
        for (int block : blocks) {
            pq.add(block);
        }

        // 当优先队列中的元素数量大于1时，继续合并操作
        while (pq.size() > 1) {
            // 取出最小的元素
            int smallest = pq.poll();
            // 取出第二小的元素
            int secondSmallest = pq.poll();
            // 合并这两个元素，新的时间为split加上第二小的元素
            pq.add(split + secondSmallest);
        }

        // 最终优先队列中只剩一个元素，即最小构建时间
        return pq.poll();
    }
}