Medium

题目描述

你是一家使用各种金属类型制造合金的公司的老板。有 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 个合金，我们需要购买：
- 第 1 种金属 2 个单位
- 第 2 种金属 2 个单位  
- 第 3 种金属 2 个单位
总计需要 2 * 1 + 2 * 2 + 2 * 3 = 12 枚硬币，小于等于预算 15。

示例 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 个合金，我们需要购买：
- 第 1 种金属 5 个单位
- 第 2 种金属 5 个单位
- 第 3 种金属 0 个单位
总计需要 5 * 1 + 5 * 2 + 0 * 3 = 15 枚硬币。

示例 3：

输入：n = 2, k = 3, budget = 10, composition = [[2,1],[1,2],[1,1]], stock = [1,1], cost = [5,5]
输出：2
解释：最佳策略是使用第 3 台机器制造合金。

约束条件：

  • 1 <= n, k <= 100
  • 0 <= budget <= 10^8
  • composition.length == k
  • composition[i].length == n
  • 1 <= composition[i][j] <= 100
  • stock.length == cost.length == n
  • 0 <= stock[i] <= 10^8
  • 1 <= cost[i] <= 100

解题思路

这是一道典型的二分搜索问题。核心思路是对每台机器尝试用二分搜索找到在预算范围内能制造的最大合金数量。

解题思路：

  1. 枚举机器：由于所有合金必须用同一台机器制造，我们需要遍历每台机器，找出每台机器能制造的最大合金数量，然后取最大值。

  2. 二分搜索合金数量：对于每台机器，合金数量的答案具有单调性——如果能制造 x 个合金，那么一定也能制造少于 x 个的合金。因此可以用二分搜索在 [0, maxPossible] 范围内查找最大可制造数量。

  3. 计算制造成本：对于给定的机器和合金数量，计算所需的总成本。对于每种金属 j，需要的总数量是 alloys * composition[i][j]，如果库存不足，需要购买 max(0, 需要数量 - stock[j]) 个单位。

  4. 确定搜索上界：理论上最多能制造多少合金？可以设置一个较大的上界，比如 2×10^8，因为即使预算全部用来买最便宜的金属，最多也就能买这么多单位。

算法步骤：

  • 对每台机器执行二分搜索
  • 对于每个候选的合金数量，计算所需的总成本
  • 如果成本在预算范围内，尝试制造更多；否则减少数量
  • 返回所有机器中的最大值

代码实现

class Solution {
public:
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        int maxAlloys = 0;
        
        for (int i = 0; i < k; i++) {
            int left = 0, right = 200000000;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                long long totalCost = 0;
                bool valid = true;
                
                for (int j = 0; j < n; j++) {
                    long long needed = (long long)mid * composition[i][j];
                    if (needed > stock[j]) {
                        long long buy = needed - stock[j];
                        totalCost += buy * cost[j];
                        if (totalCost > budget) {
                            valid = false;
                            break;
                        }
                    }
                }
                
                if (valid) {
                    maxAlloys = max(maxAlloys, mid);
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return maxAlloys;
    }
};

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        max_alloys = 0
        
        for i in range(k):
            left, right = 0, 200000000
            while left <= right:
                mid = (left + right) // 2
                total_cost = 0
                valid = True
                
                for j in range(n):
                    needed = mid * composition[i][j]
                    if needed > stock[j]:
                        buy = needed - stock[j]
                        total_cost += buy * cost[j]
                        if total_cost > budget:
                            valid = False
                            break
                
                if valid:
                    max_alloys = max(max_alloys, mid)
                    left = mid + 1
                else:
                    right = mid - 1
        
        return max_alloys

public class Solution {
    public int MaxNumberOfAlloys(int n, int k, int budget, IList<IList<int>> composition, IList<int> stock, IList<int> cost) {
        int maxAlloys = 0;
        
        for (int i = 0; i < k; i++) {
            int left = 0, right = 200000000;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                long totalCost = 0;
                bool valid = true;
                
                for (int j = 0; j < n; j++) {
                    long needed = (long)mid * composition[i][j];
                    if (needed > stock[j]) {
                        long buy = needed - stock[j];
                        totalCost += buy * cost[j];
                        if (totalCost > budget) {
                            valid = false;
                            break;
                        }
                    }
                }
                
                if (valid) {
                    maxAlloys = Math.Max(maxAlloys, mid);
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        
        return maxAlloys;
    }
}

var maxNumberOfAlloys = function(n, k, budget, composition, stock, cost) {
    let maxAlloys = 0;
    
    for (let i = 0; i < k; i++) {
        let left = 0, right = 200000000;
        while (left <= right) {
            let mid = Math.floor((left + right) / 2);
            let totalCost = 0;
            let valid = true;
            
            for (let j = 0; j < n; j++) {
                let needed = mid * composition[i][j];
                if (needed > stock[j]) {
                    let buy = needed - stock[j];
                    totalCost += buy * cost[j];
                    if (totalCost > budget) {
                        valid = false;
                        break;
                    }
                }
            }
            
            if (valid) {
                maxAlloys = Math.max(maxAlloys, mid);
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
    }
    
    return maxAlloys;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(k × n × log(maxValue))
空间复杂度O(1)

其中 k 是机器数量，n 是金属种类数，maxValue 是二分搜索的上界（约为 2×10^8）。