题解 | #最大养牛利润#

知识点：贪心

思路：子问题最优解法：在满足条件的情况下，首先饲养利润最大的牛，因为牛的成本和售价已经给出

利润就是固定的，那我每次选择最大的利润，（子问题最优解）

最后，这种解法的全局最优解，就是获取最大的利润。

综上，我们只需要每次选最大的利润，就可以解决这道题

编程语言：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;
    }
}