调试中...
中等
相关标签
相关企业
提示
给你两个长度分别为 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
解释：
- 第 0 个药水的准备从时间
t = 0开始，并在时间t = 3完成。 - 第 1 个药水的准备从时间
t = 1开始，并在时间t = 4完成。 - 第 2 个药水的准备从时间
t = 2开始，并在时间t = 5完成。
示例 3：
输入： skill = [1,2,3,4], mana = [1,2]
输出： 21
提示：
n == skill.lengthm == mana.length1 <= n, m <= 50001 <= mana[i], skill[i] <= 5000
通过次数
2.6K
提交次数
5.8K
通过率
44.3%
相关企业
提示 1
Maintain each wizard's earliest free time (for the last potion) as
f[i].提示 2
Let
x be the current mana value. Starting from now = f[0], update now = max(now + skill[i - 1] * x, f[i]) for i in [1..n]. Then, the final f[n - 1] = now + skill[n - 1] * x for this potion.提示 3
Update all other
f values by f[i] = f[i + 1] - skill[i + 1] * x for i in [0..n - 2] (in reverse order).评论 (0)
贡献者
© 2025 领扣网络（上海）有限公司
0 人在线