本文主要是介绍LeetCode 2861. 最大合金数，二分查找，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目
1、题目描述
假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有
n种不同类型的金属可以使用，并且你可以使用k台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。对于第
i台机器而言，创建合金需要composition[i][j]份j类型金属。最初，你拥有stock[i]份i类型金属，而每购入一份i类型金属需要花费cost[i]的金钱。给你整数
n、k、budget，下标从 1 开始的二维数组composition，两个下标从 1 开始的数组stock和cost，请你在预算不超过budget金钱的前提下，最大化 公司制造合金的数量。所有合金都需要由同一台机器制造。
返回公司可以制造的最大合金数。
2、接口描述
class Solution {
public:int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>>& composition, vector<int>& stock, vector<int>& cost) {}
};3、原题链接
2861. 最大合金数
二、解题报告
1、思路分析
由于题目要求所有合金必须由一台机器制造，那么问题就很简单了。
对于每台机器，如果最大制造数目为num，那么小于num的一定也能制造，具有单调性，所以可以二分查找
对于每台机器，我们进行二分查找找到每台机器的最大制造数目，维护答案即可
2、复杂度
时间复杂度： O(nklogU) 空间复杂度：O(1)
3、代码详解
C++
class Solution
{
public:int maxNumberOfAlloys(int n, int k, int budget, vector<vector<int>> &composition, vector<int> &stock, vector<int> &cost){int ret = 0, l , r , ma = *min_element(stock.begin(), stock.end()) + budget;for (auto &v : composition){function<bool(int)> check = [&](int x) -> bool{long long s = 0;for (int i = 0; i < n; i++){if (1LL * v[i] * x > stock[i])s += (1LL* v[i] * x - stock[i]) * cost[i];if (s > budget)return false;}return true;};l = ret , r = ma + 1;while (l + 1 < r){int mid = ((r - l) >> 1) + l;(check(mid) ? l : r) = mid;}ret = l;}return ret;}
};Python3
class Solution:def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:ret, ma = 0 , min(stock) + budgetfor v in composition:def check(x:int) -> bool:s = 0for i in range(n):if stock[i] < v[i] * x:s += (v[i] * x - stock[i]) * cost[i]if s > budget:return Falsereturn True;l , r = ret , ma + 1while l + 1 < r:mid = (l + r) // 2if check(mid):l = midelse:r = midret = lreturn ret这篇关于LeetCode 2861. 最大合金数，二分查找的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
