LeetCode 题解工作台
最大合金数
假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。 对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 sto…
2
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·搜索·答案·空间
答案摘要
我们注意到，所有合金都需要由同一台机器制造，因此我们可以枚举使用哪一台机器来制造合金。 对于每一台机器，我们可以使用二分查找的方法找出最大的整数 ，使得我们可以使用这台机器制造 份合金。找出所有 中的最大值即为答案。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·搜索·答案·空间 题型思路
题目描述
假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。
对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[x] 份 x 类型金属，而每购入一份 x 类型金属需要花费 cost[x] 的金钱。
给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。
所有合金都需要由同一台机器制造。
返回公司可以制造的最大合金数。
示例 1：
输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,0], cost = [1,2,3] 输出：2 解释：最优的方法是使用第 1 台机器来制造合金。 要想制造 2 份合金，我们需要购买： - 2 份第 1 类金属。 - 2 份第 2 类金属。 - 2 份第 3 类金属。 总共需要 2 * 1 + 2 * 2 + 2 * 3 = 12 的金钱，小于等于预算 15 。 注意，我们最开始时候没有任何一类金属，所以必须买齐所有需要的金属。 可以证明在示例条件下最多可以制造 2 份合金。
示例 2：
输入：n = 3, k = 2, budget = 15, composition = [[1,1,1],[1,1,10]], stock = [0,0,100], cost = [1,2,3] 输出：5 解释：最优的方法是使用第 2 台机器来制造合金。 要想制造 5 份合金，我们需要购买： - 5 份第 1 类金属。 - 5 份第 2 类金属。 - 0 份第 3 类金属。 总共需要 5 * 1 + 5 * 2 + 0 * 3 = 15 的金钱，小于等于预算 15 。 可以证明在示例条件下最多可以制造 5 份合金。
示例 3：
输入：n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5] 输出：2 解释：最优的方法是使用第 3 台机器来制造合金。 要想制造 2 份合金，我们需要购买： - 1 份第 1 类金属。 - 1 份第 2 类金属。 总共需要 1 * 5 + 1 * 5 = 10 的金钱，小于等于预算 10 。 可以证明在示例条件下最多可以制造 2 份合金。
提示：
1 <= n, k <= 1000 <= budget <= 108composition.length == kcomposition[i].length == n1 <= composition[i][j] <= 100stock.length == cost.length == n0 <= stock[i] <= 1081 <= cost[i] <= 100
解题思路
方法一：二分查找
我们注意到，所有合金都需要由同一台机器制造，因此我们可以枚举使用哪一台机器来制造合金。
对于每一台机器，我们可以使用二分查找的方法找出最大的整数 ，使得我们可以使用这台机器制造 份合金。找出所有 中的最大值即为答案。
时间复杂度 ，其中 是二分查找的上界，本题中 。空间复杂度 。
class Solution:
def maxNumberOfAlloys(
self,
n: int,
k: int,
budget: int,
composition: List[List[int]],
stock: List[int],
cost: List[int],
) -> int:
ans = 0
for c in composition:
l, r = 0, budget + stock[0]
while l < r:
mid = (l + r + 1) >> 1
s = sum(max(0, mid * x - y) * z for x, y, z in zip(c, stock, cost))
if s <= budget:
l = mid
else:
r = mid - 1
ans = max(ans, l)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n * k * log(maxAlloys)) where log(maxAlloys) comes from binary search and n * k from computing metal requirements per candidate. Space complexity is O(n) for temporary arrays storing additional metals needed. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Consider edge cases where stock covers all metal requirements and no purchases are needed.
- question_mark
Be ready to explain why binary search is efficient over iterative simulation of every alloy count.
- question_mark
Discuss how to compute required metals per machine without double counting or overspending the budget.
常见陷阱
外企场景- error
Miscalculating total required metals for multiple machines leading to incorrect feasibility.
- error
Ignoring the budget limit when stock is insufficient, which may produce invalid answers.
- error
Choosing inappropriate upper bounds for binary search, causing unnecessary iterations or overflow.
进阶变体
外企场景- arrow_right_alt
Restricting machine usage to only once per alloy sequence.
- arrow_right_alt
Allowing fractional metal units and computing maximum alloys with floating point division.
- arrow_right_alt
Adding dynamic cost changes per unit purchased, requiring updated feasibility computation per iteration.