假设你是一家合金制造公司的老板,你的公司使用多种金属来制造合金。现在共有 n 种不同类型的金属可以使用,并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。

对于第 i 台机器而言,创建合金需要 composition[i][j] 份 j 类型金属。最初,你拥有 stock[i] 份 i 类型金属,而每购入一份 i 类型金属需要花费 cost[i] 的金钱。

给你整数 n、k、budget,下标从 1 开始的二维数组composition,两个下标从 1 开始的数组 stock 和 cost,请你在预算不超过 budget 金钱的前提下,最大化 公司制造合金的数量。

所有合金都需要由同一台机器制造。

输出格式

返回公司可以制造的最大合金数。

输入格式

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:

Input:

n = 3, k = 2, budget = 15, 
composition = [[1,1,1],[1,1,10]], 
stock = [0,0,0], 
cost = [1,2,3]

Output:

2

解析:

最优的方法是使用第 1 台机器来制造合金。 要想制造 2 份合金,我们需要购买:

  • 2 份第 1 类金属。
  • 2 份第 2 类金属。
  • 2 份第 3 类金属。

总共需要 2 1 + 2 2 + 2 * 3 = 12 的金钱,小于等于预算 15 。注意,我们最开始时候没有任何一类金属,所以必须买齐所有需要的金属。可以证明在示例条件下最多可以制造 2 份合金。

样例2:

Input:

n = 3, k = 2, budget = 15, 
composition = [[1,1,1],[1,1,10]], 
stock = [0,0,100], 
cost = [1,2,3]

Output:

5

解析:

最优的方法是使用第 2 台机器来制造合金。

要想制造 5 份合金,我们需要购买:

  • 5 份第 1 类金属。
  • 5 份第 2 类金属。
  • 0 份第 3 类金属。

总共需要 5 1 + 5 2 + 0 * 3 = 15 的金钱,小于等于预算 15 。 可以证明在示例条件下最多可以制造 5 份合金。

样例3:

Input:

n = 2, k = 3, budget = 10, 
composition = [[2,1],[1,2],[1,1]], 
stock = [1,1], 
cost = [5,5]

Output:

2

解析:

最优的方法是使用第 3 台机器来制造合金。

要想制造 2 份合金,我们需要购买:

  • 1 份第 1 类金属。
  • 1 份第 2 类金属。

总共需要 1 5 + 1 5 = 10 的金钱,小于等于预算 10 。 可以证明在示例条件下最多可以制造 2 份合金。


题目分析

Binary Search

代码实现

class Solution {
public:
    bool check(int mid, int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {

        for(int i = 0; i < k; ++i) {
            long long consume = 0;
            for(int j = 0; j < n; ++j) 
                consume += max(0ll, composition[i][j] * 1ll * mid - stock[j]) * 1ll * cost[j];
            if(budget >= consume) return 1;   
        } 
        return 0;
    }
    int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
        int l = 0, r = 2e8 + 10;
        while(l <= r) {
            int mid = ((r - l) >> 1) + l;
            if(check(mid, n, k, budget, composition, stock, cost)) l = mid + 1;
            else r = mid - 1;
        }
        return r;
    }
};
分类: Binary-Search

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status