leetcode-2861最大合金数

本文主要是介绍leetcode-2861最大合金数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

链接: leetcode最大合金数

解题思路

二分查找
所有合金都需要由一台机器制造，因此我们可以枚举使用哪一台机器来制造和金。

对于每一台机器，我们可以使用二分查找的方法找出最大的整数x,使得我们可以使用这台机器制造x份合金。找出所有x中的最大值即为答案。

用low和high分别表示二分查找的下界和上界。由于可以制造的最大合金数一定非负，因此low的初始值值等于0；由于当数组composition和cost中的所有的元素值都等于1时可以制造的合金数最大，为min{stock} + budget，因此high的初始值等于min{stock} + budeget。

解题代码

class Solution:def maxNumberOfAlloys(self,n: int,k: int,budget: int,composition: List[List[int]],stock: List[int],cost: List[int],) -> int:ans = 0for c in composition:l, r = 0, budget + stock[0]while l < r:mid = (l + r + 1) >> 1s = sum(max(0, mid * x - y) * z for x, y, z in zip(c, stock, cost))if s <= budget:l = midelse:r = mid - 1ans = max(ans, l)return ans

这篇关于leetcode-2861最大合金数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---