2861.最大合金数

链接：2861.最大合金数
难度：Medium
标签：数组、二分查找
简介：给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组 stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。

题解 1 - python

• 编辑时间：2024-01-27
• 执行用时：695ms
• 内存消耗：16.87MB
• 编程语言：python
• 解法介绍：二分。

class Solution:
    def maxNumberOfAlloys(self, n: int, k: int, budget: int, composition: List[List[int]], stock: List[int], cost: List[int]) -> int:
        def check(count: int, comp: List[int]) -> bool:
            return sum(cost[i] * max(count * comp[i] - stock[i], 0) for i in range(n)) <= budget
        l, r = 0, 10 ** 10
        while l < r:
            m = (l + r + 1) // 2
            if any(check(m, comp) for comp in composition):
                l = m
            else:
                r = m - 1
        return l