题解 | #最大养牛利润# 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;
        List<Pair> pairs = new ArrayList<>(); // 存储每头牛的利润和饲养成本
        for (int i = 0; i < n; ++i) {
            pairs.add(new Pair(profits[i], costs[i]));
        }
        Collections.sort(pairs,
                         Collections.reverseOrder()); // 按照利润从大到小排序

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>
        (Collections.reverseOrder()); // 最大堆，存储当前可选的牛的饲养成本
        for (int i = 0; i < n; ++i) {
            maxHeap.offer(pairs.get(i).cost);
        }

        boolean[] chosen = new
        boolean[n]; // 标记数组，记录每头牛是否被选择过饲养
        int totalProfit = w; // 总利润，初始值为初始资本 w
        for (int i = 0; i < k; ++i) {
            int maxProfit = 0;
            int chosenCow = -1;
            for (int j = 0; j < n; ++j) {
                if (!chosen[j] && pairs.get(j).cost <= totalProfit) {
                    // 如果该牛没有被选择过饲养，并且当前资本足够饲养该牛
                    if (pairs.get(j).profit > maxProfit) {
                        // 更新最大利润和被选择的牛的索引
                        maxProfit = pairs.get(j).profit;
                        chosenCow = j;
                    }
                }
            }
            if (chosenCow == -1) {
                // 如果没有可选的牛，说明已经选满了 k 头牛，退出循环
                break;
            }
            chosen[chosenCow] = true; // 将该牛标记为已被选择
            totalProfit += maxProfit; // 将该牛的利润加到总利润上
        }

        return totalProfit - w; // 输出不包括初始资本
    }

    class Pair implements Comparable<Pair> {
        int profit;
        int cost;

        Pair(int p, int c) {
            profit = p;
            cost = c;
        }

        @Override
        public int compareTo(Pair other) {
            return Integer.compare(profit, other.profit);
        }
    }
}

编程语言是 Java。

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

1. 贪心算法
2. 排序算法
3. 堆数据结构

代码的文字解释如下：

1. 将每头牛的利润和成本存储在 pairs 列表中，然后按照利润从大到小对牛进行排序。
2. 使用 PriorityQueue 来构建最大堆，将所有牛的成本添加到堆中。
3. 使用布尔数组 chosen 来标记每头牛是否被选择饲养。
4. 使用 totalProfit 变量来记录总利润，初始值为初始资本 w。
5. 在循环中，选择每一轮最优的牛进行饲养：遍历每头牛，找到在当前资本下利润最高的可选牛。
6. 如果找到可选的牛，将其标记为已被选择，将其利润加到总利润中。
7. 返回总利润与初始资本之差，即最终可获得的最大利润