题解
因为暴力会超时
合成合金num
越少花费越少,合成越多花费越多具有单调性
故可以通过二分答案来完成该题
遍历每一台机器,对最多可合成合金数量进行二分
用每一个mid
求一下合成mid
数量的合金需要花费cst
元
二分的边界即为预算budget >= cst
C++ 代码
class Solution {
public:
int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
int res = 0;
for(int i = 0; i < k; i++){
int l = 0, r = 2e8;
while(l < r){
int mid = (l + r + 1) / 2;
//接下来以合成mid数量的合金为条件求一下所需的费用cst
long long cst = 0;
for(int j = 0; j < n && cst <= budget; j++){
if((long long)mid * composition[i][j] - stock[j] > 0)
cst += ((long long)mid * composition[i][j] - stock[j]) * cost[j];
}
if(cst <= budget) l = mid;
else r = mid - 1;
}
res = max(res, l);
}
return res;
}
};