3494.酿造药水需要的最少总时间

implementation, https://leetcode.cn/problems/find-the-minimum-amount-of-time-to-brew-potions/

给你两个长度分别为 n 和 m 的整数数组 skill 和 mana 。

在一个实验室里，有 n 个巫师，他们必须按顺序酿造 m 个药水。每个药水的法力值为 mana[j]，并且每个药水 必须 依次通过 所有 巫师处理，才能完成酿造。第 i 个巫师在第 j 个药水上处理需要的时间为 timeij = skill[i] * mana[j]。

由于酿造过程非常精细，药水在当前巫师完成工作后 必须 立即传递给下一个巫师并开始处理。这意味着时间必须保持 同步，确保每个巫师在药水到达时 马上 开始工作。

返回酿造所有药水所需的 最短 总时间。

示例 1：

输入： skill = [1,5,2,4], mana = [5,1,4,2]

输出： 110

解释：

药水编号	开始时间	巫师 0 完成时间	巫师 1 完成时间	巫师 2 完成时间	巫师 3 完成时间
0	0	5	30	40	60
1	52	53	58	60	64
2	54	58	78	86	102
3	86	88	98	102	110

举个例子，为什么巫师 0 不能在时间 t = 52 前开始处理第 1 个药水，假设巫师们在时间 t = 50 开始准备第 1 个药水。时间 t = 58 时，巫师 2 已经完成了第 1 个药水的处理，但巫师 3 直到时间 t = 60 仍在处理第 0 个药水，无法马上开始处理第 1个药水。

示例 2：

输入： skill = [1,1,1], mana = [1,1,1]

输出： 5

解释：

1. 第 0 个药水的准备从时间 t = 0 开始，并在时间 t = 3 完成。
2. 第 1 个药水的准备从时间 t = 1 开始，并在时间 t = 4 完成。
3. 第 2 个药水的准备从时间 t = 2 开始，并在时间 t = 5 完成。

示例 3：

输入： skill = [1,2,3,4], mana = [1,2]

输出： 21

提示：

• n == skill.length
• m == mana.length
• 1 <= n, m <= 5000
• 1 <= mana[i], skill[i] <= 5000

implementation

【灵茶山艾府】思路：为了计算酿造药水的时间，定义 lastFinish[i] 表示巫师 i 完成上一瓶药水的时间。

示例 1 在处理完 mana[0] 后，有

lastFinish=[5,30,40,60] 如果接着 lastFinish 继续酿造下一瓶药水 mana[1]=1，完成时间是多少？注意开始酿造的时间不能早于 lastFinish[i]。

i	skill[i]	lastFinish[i]	完成时间
0	1	5	5+1=6
1	5	30	max(6,30)+5=35
2	2	40	max(35,40)+2=42
3	4	60	max(42,60)+4=64

题目要求「药水在当前巫师完成工作后必须立即传递给下一个巫师并开始处理」，也就是说，酿造药水的过程中是不能有停顿的。

从 64 开始倒推，可以得到每名巫师的实际完成时间。比如倒数第二位巫师的完成时间，就是 64 减去最后一名巫师花费的时间 4⋅1，得到 60。

i	skill[i]	实际完成时间
3	4	64
2	2	64−4⋅1=60
1	5	60−2⋅1=58
0	1	58−5⋅1=53

按照上述过程处理每瓶药水，最终答案为 lastFinish[n−1]。

from typing import List

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)  # 巫师的数量
        last_completion = [0] * n  # last_completion[i] 表示巫师 i 处理完上一瓶药水的时间

        # 依次处理每瓶药水
        for potion_mana in mana:
            current_time = 0  # 当前药水开始处理的时间

            # **第一阶段：正向遍历所有巫师，计算药水完成时间**
            for i in range(n):
                # 确保当前巫师不会比上一瓶药水的完成时间更早开始
                #current_time = max(current_time, last_completion[i])
                if last_completion[i] > current_time: current_time = last_completion[i]  # 手写 max
                # 巫师 i 处理当前药水所需时间
                current_time += skill[i] * potion_mana

            # **第二阶段：逆向更新 last_completion，确保后续药水可以无缝衔接**
            last_completion[-1] = current_time  # 最后一个巫师的完成时间
            for i in range(n - 2, -1, -1):
                # 由于巫师 i+1 处理当前药水所需时间是 skill[i+1] * potion_mana
                current_time -= skill[i + 1] * potion_mana
                last_completion[i] = current_time  # 巫师 i 应该何时完成当前药水

        return last_completion[-1]  # 返回最后一个药水的完成时间

if __name__ == '__main__':
    sol = Solution()
    skill1 = [1, 5, 2, 4]
    mana1 = [5, 1, 4, 2]
    print(sol.minTime(skill1, mana1))  # 输出 110

下面给出一个 Python 解法，它利用前缀和以及对每个药水计算起始时间的“推迟量”来满足各个巫师之间立即传递的约束。关键思想是定义一个变量

$x[j]$ 表示第 (j) 个药水在巫师 0 上开始处理的时间，然后利用下面的不等式约束：

• 对于第 0 个巫师，其要求是

  $x[j]\ge x[j-1]+\text{skill}[0]\times \text{mana}[j-1].$

• 对于 $i\ge 1$ 的巫师，考虑药水在连续传递时必须无缝对接。可以证明为了保证所有巫师都“立刻”开始处理，第 j 个药水的起始时间必须满足对于所有 $1\le i<n$

  $x[j]\ge x[j-1]+\text{skill}[i]\times \text{mana}[j-1]+(\sum _{k=0}^{i-1}\text{skill}[k])\times (\text{mana}[j-1]-\text{mana}[j]).$

因此，我们令

$x[j]=\underset{0\le i<n}{max}\{x[j-1]+\mathrm{\Delta }(i,j)\},$

其中当 (i=0) 时

$\mathrm{\Delta }(0,j)=\text{skill}[0]\times \text{mana}[j-1],$

而当 $i\ge 1$ 时

$\mathrm{\Delta }(i,j)=\text{skill}[i]\times \text{mana}[j-1]+(\sum _{k=0}^{i-1}\text{skill}[k])\times (\text{mana}[j-1]-\text{mana}[j]).$

处理完所有 (m) 个药水以后，总耗时为

$x[m-1]+(\sum _{k=0}^{n-1}\text{skill}[k])\times \text{mana}[m-1],$

其中后半项表示最后一个药水经过所有巫师的加工时间。

from typing import List

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        n = len(skill)
        m = len(mana)
        prefix = [0] * n
        prefix[0] = skill[0]
        for i in range(1, n):
            prefix[i] = prefix[i - 1] + skill[i]

        x = 0
        for j in range(1, m):
            pre = mana[j-1]
            cur = mana[j]

            max_v = x + skill[0] * pre
            for i in range(1, n):
                max_v = max(max_v, x + skill[i] * pre + prefix[i-1] * (pre - cur))

            x = max_v

        ans = x + prefix[-1] * mana[-1]
        return ans

if __name__ == "__main__":
    sol = Solution()
    print(sol.minTime([1,5,2,4], [5,1,4,2]))
    print(sol.minTime([1,1,1], [1,1,1]))
    print(sol.minTime([1,2,3,4], [1,2]))

说明

1. 前缀和的作用
   预先计算前 i 个巫师的技能和，这样在计算每个候选值时可以迅速获得 $\sum _{k=0}^{i-1}\text{skill}[k]$ 的值。

2. 逐药水更新
   依次处理药水 1 至 m-1（第 0 个药水的起始时间定为 0），每次根据所有巫师给出的约束计算出最晚的必要起始时间，保证后续传递过程中各个巫师能够“立即”接手。

3. 最终耗时计算
   最后一个药水在巫师 0 开始的时间加上经过所有巫师的处理时间就是总耗时。

这种方法的时间复杂度是 $O(m\times n)$，使得即使 n, m 较大时效率也能接受。