题解 | #最大养牛利润# 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 temp = w;
        int[][] cows = new int[n][2];
        for (int i = 0; i < n; i++) {
            cows[i][0] = costs[i];
            cows[i][1] = profits[i];
        }

        Arrays.sort(cows, (a, b) -> a[0] - b[0]);

        PriorityQueue<Integer> q = new PriorityQueue<>((a, b) -> b - a);
        int cur = 0;
        for (int i = 0; i < k; i++) {
            while (cur < n && cows[cur][0] <= w) {
                q.offer(cows[cur][1]);
                cur++;
            }
            if (!q.isEmpty()) {
                w += q.poll();
            } else {
                break;
            }
        }

        return w - temp;
    }
}

该题主要考察的知识点包括：

1. 二维数组的使用：代码中使用二维数组cows来存储每头牛的成本和利润。数组中的每个元素是一个二元组，第一个元素表示成本，第二个元素表示利润。
2. 排序：利用Arrays.sort()方法或std::sort()函数对牛按照成本进行升序排序。通过排序，可以方便地找到成本小于等于当前资本的牛。
3. 优先队列（PriorityQueue）的使用：代码中使用优先队列q来维护利润的最大堆。优先队列会自动根据指定的比较器（Lambda表达式）对元素进行排序，以保证队列头部元素始终是最大的利润。
4. 贪心算法思想：在购买阶段，从排好序的牛中选择成本小于等于当前资本的牛，并将它们的利润加入优先队列。在每次购买时，从优先队列中获取利润最大的牛，并更新当前资本。重复这个过程，直到购买次数达到上限或者无法购买更多牛为止。

代码解释：

• 定义一个名为findMaximizedProfits的方法，接受四个参数：k表示可购买的数量，w表示初始资本，profits表示每头牛的利润数组，costs表示每头牛的成本数组。
• 创建一个二维数组cows，用于存储每头牛的成本和利润。数组的大小为牛的数量，并将成本和利润分别赋值给对应的元素。
• 使用Java的排序方法（如Arrays.sort()）对cows数组进行排序，按照成本升序排列。
• 创建一个优先队列q，用于存储利润的最大堆。使用优先队列的构造函数，传入一个Lambda表达式作为比较器，以实现降序排列。
• 创建一个变量cur，用于追踪当前遍历到的牛的索引。
• 使用循环来购买牛，循环次数为k，表示可购买的数量。
• 在循环中，通过while循环遍历牛，将满足成本小于等于当前资本的牛的利润加入优先队列。如果当前牛的成本小于等于当前资本，则将牛的利润加入优先队列，并更新cur的值，向后移动一位。
• 在购买阶段，首先检查优先队列是否为空，如果为空则跳出循环，表示无法再购买更多的牛。
• 如果优先队列不为空，则从队列中取出利润最大的牛，更新当前资本，即将其加到w上。
• 循环结束后，返回最终资本与初始资本之间的差值，即实际获得的利润。