题解 | #最大养牛利润#

最大养牛利润

https://www.nowcoder.com/practice/c12d61e3126a4f59a9587d056fb41fdb

题目考察的知识点是:

贪心算法、优先队列

题目解答方法的文字分析:

问题最优解法:在满足条件的情况下,首先饲养利润最大的牛,因为牛的成本和售价已经给出.利润就是固定的,那我每次选择最大的利润,最后,这种解法的全局最优解,就是获取最大的利润。

本题解析所用的编程语言:

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 收藏 评论
分享
牛客网
牛客企业服务