题解 | #最大养牛利润#

最大养牛利润

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;
    }
}

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-15 17:46
暑期就挂了,秋招还有机会吗
大聪明777:研发提前批,14号刚开的,官网上面的配图上有写。提前批没过的话,秋招还可以投,不过前面的笔试/面试记录会被保留,供秋招参考
26届校招投递进展
点赞 评论 收藏
分享
风中翠竹:真的真的真的没有kpi。。。面试官是没有任何kpi的,捞是真的想试试看这个行不行,碰碰运气,或者是面试官比较闲现在,没事捞个人看看。kpi算HR那边,但是只有你入职了,kpi才作数,面试是没有的。
双非有机会进大厂吗
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务