题解 | #最大养牛利润#
最大养牛利润
https://www.nowcoder.com/practice/c12d61e3126a4f59a9587d056fb41fdb
知识点:贪心
思路:子问题最优解法:在满足条件的情况下,首先饲养利润最大的牛,因为牛的成本和售价已经给出
利润就是固定的,那我每次选择最大的利润,(子问题最优解)
最后,这种解法的全局最优解,就是获取最大的利润。
综上,我们只需要每次选最大的利润,就可以解决这道题
编程语言:java
如果我的思路启发了你,给个小小关注吧~
我是废江,一个从java跑到内核再准备润回java的打工人,我会持续分享从linux内核到上层java微服务等干货
import java.util.*; import java.util.stream.Collectors; import java.util.stream.IntStream; 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 //创建排序索引 List<Integer> indices = IntStream.range(0, profits.length) .boxed() .sorted(Comparator.comparingInt(i -> profits[i])) .collect(Collectors.toList()); //应用索引规则 int[] sortProfits = indices.stream().mapToInt(i -> profits[i]).toArray(); int[] sortCost = indices.stream().mapToInt(i ->costs[i]).toArray(); int ww = w,cur = sortProfits.length - 1; while (cur >= 0) { //之前思路的最优解,每次挑利润最大的 if (sortCost[cur] <= w && k > 0) { //买得起! w = w + sortProfits[cur];//累计利润 sortCost[cur] = Integer.MAX_VALUE;//防止重复买 cur = sortProfits.length - 1;//买完重新挑 k--;//可买数量-1 continue; } cur--; } return w-ww; } }