题解 | #最大养牛利润#

理解易错点: 本题中计算的最大利润实际是profits的数据累加的结果

每头牛实际只能饲养一次

理解这两点之后就好计算了

方法一:来自@不太迷人的反派_的算法,排序索引

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());
        //应用索引规则,重新对应profit与cost的关系
        int[] sortProfits = indices.stream().mapToInt(i -> profits[i]).toArray();
        int[] sortCost = indices.stream().mapToInt(i ->costs[i]).toArray();

        int sum = 0, cur = sortProfits.length - 1;
        while (cur >= 0) {
            //之前思路的最优解，每次挑利润最大的
            if (sortCost[cur] <= w && k > 0) {
                //买得起！
                sum = sum + sortProfits[cur];//累加售价
                w = w + sortProfits[cur];//当前资本
                k--;
                sortCost[cur] = Integer.MAX_VALUE;//每头牛只能饲养一次??
                cur = sortProfits.length - 1;//重新由最大利润寻找
                continue;
            }
            cur--;
        }
        return sum;
    }
}

方法二:定义新类型,自定义排序规则

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整型
     */
    static class Cow implements Comparable {
        int profit, cost;
        Cow(int profit, int cost) {
            this.profit = profit;
            this.cost = cost;
        }
        @Override
        public String toString() {
            return "[" + profit + "," + cost + "]";
        }
        @Override
        public int compareTo(Object o) {//成本低利润高
            Cow t = (Cow) o;
            int result = t.profit > profit ? 1 : (t.profit == profit ? 0 : -1);
            if (result == 0) {
                result = t.cost < t.cost ? 1 : -1;
            }
            return result;
        }
    }
    public static int findMaximizedProfits (int k, int w, int[] profits,
                                            int[] costs) {
        ArrayList<Cow> cows = new ArrayList<>();
        int n = profits.length;
        for (int i = 0; i < n; i++) {
            cows.add(new Cow(profits[i], costs[i]));
        }
        Collections.sort(cows);
        int temp = w, cur = 0;
        while(cur<n) {
            //之前思路的最优解，每次挑利润最大的
            if (cows.get(cur).cost <= w && k > 0) {
                //买得起！
                w = w + cows.get(cur).profit;
                cows.remove(cur);
                k--;n--;//此处注意n--防止溢出,当然按照上一种改为MAX_VALUE也是可以的
                cur=0;
                continue;
            }
            cur++;
        }
        return w - temp;
    }
}