最开始做这道题的时候没想到用这种方法,我之后也在想二分查找法什么时候能用。
其本质上还是在有序的范围中找到目标的数。这道题也就是要找到最大的合金数。
最基本的二分查找题目就是找到具体的那个数,等不等于那个数就是作为限制条件。
那这一题呢就是花费要小于限定值。
因此不断遍历每个机器找到所需花费,如果找到一个机器在目前合金数下能实现(就是小于花费的限定值)。就直接返回,因为求的就是合金数,能找到一种情况直接返回就行了。
具体代码:
点击查看代码
class Solution {
public:
int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {
int left=0;int right=2e8;int mid=0;int ans=0;
while(left<=right){
bool flag=false;
mid=(left+right)/2;
for(int i=0;i<composition.size();i++){
long long spend=0;
for(int j=0;j<composition[i].size();j++){
spend += max(static_cast<long long>(composition[i][j]) * mid - stock[j], 0LL) * cost[j];
}
if(spend<=budget){
flag=true;
break;
}
}
if(flag){
ans=mid;
left=mid+1;
}
else{
right=mid-1;
}
}
return ans;
}
};