题解 | #最大养牛利润#
最大养牛利润
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; } }#题解#