二分查找
所有合金都要由同一台机器制造,所以答案就是各机器单独生产合金数的最大值。
对于某一台机器而言,制造的合金越多,需要的钱就越多,当合金数num
超过一个合法数时,需要的钱就会超过budget
,说明num
具有二分性,可以对每一台机器能够生产出的最大合金数进行二分查找。最后更新所有机器中能够制造的最大合金数量。
时间复杂度: $O(knlog(min(stock) + budget)$
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(auto& machine : composition) {
function<bool(long long)> check = [&](long long mid) -> bool {
long long money = 0;
for(int i = 0; i < n; i++) {
// 若某类金属需要的数量大于库存,需要花钱购买
if(stock[i] < machine[i] * mid)
money += ((machine[i] * mid) - stock[i]) * cost[i];
if(money > budget)
return false;
}
return true;
};
// 二分查找当前机器能够生产的最大合金数
int l = 0, r = 1e9;
while(l < r) {
int mid = ((r - l) >> 1) + l + 1;
if(check((long long)mid)) l = mid;
else r = mid - 1;
}
res = max(res, l);
}
return res;
}
};