题解 | #最大养牛利润#

知识点

贪心

解题思路

使用优先队列来存储一个数组，其中cow[0]表示利润，cow[1]表示饲养成本，利润最大的牛排在队列的前面。

我们将所有牛的利润加入优先队列。由于优先队列是一个最大堆，默认情况下队首元素是利润最大的牛。

然后，我们通过遍历k次的循环来选择饲养k头牛。在每次循环中，如果队列为空或者资本不足以饲养当前利润最大的牛，则将该牛放入到暂存队列中。

否则，我们从队列中取出利润最大的牛，更新可用资本w并加上该牛的利润，将暂存队列中支付不起的牛又放回队列中，然后进入下一次循环。

最终，返回更新后的可用资本w减去成本即可得到最终可获得的最大利润。

Java题解

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param k int整型
     * @param w int整型
     * @param profits int整型一维数组
     * @param costs int整型一维数组
     * @return int整型
     */
    public int findMaximizedProfits (int k, int w, int[] profits, int[] costs) {
        // write code here
        int n = profits.length;
        int baseW = w; //初始成本
        // 创建一个优先队列，用于按照利润将牛排序
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (b[0] - a[0]));
        for (int i = 0; i < n; i++) {
            pq.offer(new int[] {profits[i], costs[i]});
        }

        for (int i = 0; i < k; i++) {
            // 创建一个临时队列，用于存储可饲养的牛
            PriorityQueue<int[]> tempPq = new PriorityQueue<>((a, b) -> (b[0] - a[0]));

            // 将支付不起的牛放进tempPq
            while (!pq.isEmpty() && w < pq.peek()[1]) {
                int[] cow = pq.poll();
                tempPq.offer(cow);
            }

            // 如果没有可饲养的牛，则结束循环
            if (pq.isEmpty()) {
                break;
            } else {
                int[] cow = pq.poll();
                w += cow[0];
            }

            // 将临时队列中的牛重新放回优先队列
            while (!tempPq.isEmpty()) {
                pq.offer(tempPq.poll());
            }
        }

        return w - baseW;
    }
}