class Solution {
public:
int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
}
};
100033. 最大合金数
假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。
对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有 stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。
给你整数 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原站题解
python3 解法, 执行用时: 139 ms, 内存消耗: 17.1 MB, 提交时间: 2024-01-27 15:54:37
class Solution:
def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
ans = 0
mx = min(stock) + budget
for comp in composition:
def f(num: int) -> int:
money = 0
for s, base, c in zip(stock, comp, cost):
if s < base * num:
money += (base * num - s) * c
if money > budget:
break
return money
ans += bisect_right(range(ans + 1, mx + 1), budget, key=f)
return ans
python3 解法, 执行用时: 208 ms, 内存消耗: 16.7 MB, 提交时间: 2023-09-17 22:42:51
class Solution:
def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
ans = 0
mx = min(stock) + budget
for com in composition:
def check(num: int) -> int:
money = 0
for s, base, c in zip(stock, com, cost):
if s < base * num:
money += (base * num - s) * c
if money > budget:
return False
return True
left, right = 0, mx + 1
while left + 1 < right: # 开区间写法
mid = (left + right) // 2
if check(mid):
left = mid
else:
right = mid
ans = max(ans, left)
return ans
java 解法, 执行用时: 19 ms, 内存消耗: 42.5 MB, 提交时间: 2023-09-17 22:42:37
class Solution {
public int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
int ans = 0;
int mx = Collections.min(stock) + budget;
for (var com : composition) {
int left = 0, right = mx + 1;
while (left + 1 < right) { // 开区间写法
int mid = (left + right) / 2;
boolean ok = true;
long money = 0;
for (int i = 0; i < n; ++i) {
if (stock.get(i) < com.get(i) * mid) {
money += ((long) com.get(i) * mid - stock.get(i)) * cost.get(i);
if (money > budget) {
ok = false;
break;
}
}
}
if (ok) {
left = mid;
} else {
right = mid;
}
}
ans = Math.max(ans, left);
}
return ans;
}
}
cpp 解法, 执行用时: 52 ms, 内存消耗: 54 MB, 提交时间: 2023-09-17 22:42:25
class Solution {
public:
int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>> &composition, vector<int> &stock, vector<int> &cost) {
int ans = 0;
int mx = *min_element(stock.begin(), stock.end()) + budget;
for (auto &com: composition) {
auto check = [&](long long num) -> bool {
long long money = 0;
for (int i = 0; i < n; i++) {
if (stock[i] < com[i] * num) {
money += (com[i] * num - stock[i]) * cost[i];
if (money > budget) {
return false;
}
}
}
return true;
};
int left = 0, right = mx + 1;
while (left + 1 < right) { // 开区间写法
int mid = (left + right) / 2;
(check(mid) ? left : right) = mid;
}
ans = max(ans, left);
}
return ans;
}
};
golang 解法, 执行用时: 32 ms, 内存消耗: 6.6 MB, 提交时间: 2023-09-17 22:42:10
func maxNumberOfAlloys(_, _, budget int, composition [][]int, stock, cost []int) (ans int) {
mx := stock[0]
for _, s := range stock {
mx = min(mx, s)
}
mx += budget
for _, com := range composition {
res := sort.Search(mx, func(num int) bool {
num++
money := 0
for i, s := range stock {
if s < com[i]*num {
money += (com[i]*num - s) * cost[i]
if money > budget {
return true
}
}
}
return false
})
ans = max(ans, res)
}
return
}
func min(a, b int) int { if b < a { return b }; return a }
func max(a, b int) int { if b > a { return b }; return a }
javascript 解法, 执行用时: 84 ms, 内存消耗: 43.8 MB, 提交时间: 2023-09-17 22:41:53
/**
* @param {number} n
* @param {number} k
* @param {number} budget
* @param {number[][]} composition
* @param {number[]} stock
* @param {number[]} cost
* @return {number}
*/
var maxNumberOfAlloys = function (n, k, budget, composition, stock, cost) {
let ans = 0;
const mx = Math.min(...stock) + budget;
for (const com of composition) {
function check(num) {
let money = 0;
for (let i = 0; i < n; i++) {
if (stock[i] < com[i] * num) {
money += (com[i] * num - stock[i]) * cost[i];
if (money > budget) {
return false;
}
}
}
return true;
}
let left = 0, right = mx + 1;
while (left + 1 < right) { // 开区间写法
const mid = (left + right) >> 1;
if (check(mid)) {
left = mid;
} else {
right = mid;
}
}
ans = Math.max(ans, left);
}
return ans;
};