题解 | #最大养牛利润#

• 题目考察的知识点 : 贪心算法
• 题目解答方法的文字分析：

1. 首先将每头牛的成本和利润存储在一个 tuple 中，并使用 sort 对所有牛按照成本从小到大排序。然后，我们使用一个 list 来保存当前能够购买的牛。接下来，我们依次考虑还能够购买的牛，直到购买了 k 头牛或者无法继续购买为止。对于每个能够购买的牛，如果它的成本小于等于当前可用的资本 w，则将它的利润加入最大堆 q 中；否则，说明它无法购买，不需要继续考虑。接着，我们从最大堆 q 中弹出堆顶元素，并将其加入当前可用的资本 w 中。最后，我们返回可获得的最大利润。

• 本题解析所用的编程语言: Python
• 完整且正确的编程代码

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param k int整型
# @param w int整型
# @param profits int整型一维数组
# @param costs int整型一维数组
# @return int整型
#
import heapq


class Solution:
    def findMaximizedProfits(
        self, k: int, w: int, profits: List[int], costs: List[int]
    ) -> int:
        temp = w # 记录初始资本
        cows = [(costs[i], profits[i]) for i in range(len(profits))]
        cows.sort() # 将所有牛按照成本从小到大排序
        q = [] # 最大堆（优先队列）
        cur = 0
        for i in range(k): # 购买 k 头牛
            while cur < len(cows) and cows[cur][0] <= w: # 将所有成本小于等于 w 的牛加入最大堆中
                heapq.heappush(q, -cows[cur][1])
                cur += 1
            if q: # 如果最大堆非空，则选择堆顶元素购买
                w += -heapq.heappop(q)
            else: # 如果最大堆为空，则无法继续购买牛
                break
        return w - temp # 返回可获得的最大利润