MarsCode算法题之贪心猫的鱼干大分配

2024-11-09 21:25:41

1.问题描述

假如有一群猫排成一行，要分配鱼干，每一只猫都有一个等级值。你作为管理员有很多鱼干但是需要按下边的分配制度分配：

每一只猫至少要分配一斤鱼干，鱼干分配最小单位是斤，必须保证是整数。
猫比他们邻居有更高等级值的分配的鱼干要多于他们的邻居。

为了满足上边的分配规则，需要得到需要的最少鱼干数量。

示例1

第 1 行输入猫的数量 N

从第 2 行到第 N + 1 行，输入每一只猫的等级值 D。

输入样例

3
1
2
2

输出样例

4

提示

1 <= N <= 10^3

1 <= D <= 10^6

难度等级

中等

题目链接

贪心猫的鱼干大分配

2.解题思路

这道题目叫做贪心猫的鱼干大分配，题目直接就告诉我们该用贪心算法来AC这道题了。

首先，我们要初始化一个存储每只猫的鱼干数组，并且按照题目要求，每只猫至少一斤鱼干，将数组的值初始化为1。

        int[] cat = new int[n];
        //初始化每只猫至少一斤鱼干
        for(int i = 0;i < n;i++){
            cat[i] = 1;
        }

题目要求猫如果等级比邻居高，那么分配的鱼干也要比邻居多，这就涉及到了左右的比较。我们可以把左右的比较拆开来，先和左边的比较，然后再返过来和右边的比较。

用一个for循环从左向右遍历，如果当前这只猫的等级比它左边的猫高，那么当前这只猫的鱼干就要比左边那只猫多一斤(因为要求最少的鱼干，所以我们只给多一斤，贪心资本家的体现)，如果等级和左边的猫相等或者比左边的猫小，不做处理，还是一斤。我们这一轮循环主要解决左边的猫比当前猫等级大的情况。遍历完成之后，就确保了，每一只猫，如果左边的猫比自己等级小，鱼干一定比自己少。

        //从左到右遍历
        for(int i = 1;i < n;i++){
            if(cats_levels.get(i) > cats_levels.get(i-1)){
                cat[i] = cat[i-1]+1;
            }
        }

接着，再用一个for循环从右向左遍历，如果当前这只猫的等级比它右边的猫高。那么当前这只猫的鱼干至少要比右边那只猫多一斤，但是我们还要保持如果比左边的猫等级高，当前猫的鱼干也要比左边多，所以我们要在当前猫已经有的鱼干和比右边那只猫的鱼干多一斤这两个数量中取最大值，这样才能同时满足猫如果等级比左右邻居高，那么分配的饼干也要比左右邻居多。遍历完成之后，就确保了，每一只猫，如果右边的猫比自己等级小，鱼干一定比自己少。

        //从右到左遍历
        for(int i = n-2;i >=0;i--){
            if(cats_levels.get(i) > cats_levels.get(i+1)){
                cat[i] = Math.max(cat[i],cat[i+1]+1);
            }
        }

两个循环遍历下来，我们已经解决了猫的鱼干数量问题，最后统计一下每只猫的鱼干，累加起来就是所需鱼干的最小总数了。

         int result = 0;
        //计算总鱼干数
        for(int i = 0;i < n;i++){
            result += cat[i];
        }

3.代码展示

import java.util.ArrayList;
import java.util.List;

public class Main {
    public static int solution(int n, List<Integer> cats_levels) {
        // Please write your code here
        int[] cat = new int[n];
        //初始化每只猫至少一斤鱼干
        for(int i = 0;i < n;i++){
            cat[i] = 1;
        }
        //从左到右遍历
        for(int i = 1;i < n;i++){
            if(cats_levels.get(i) > cats_levels.get(i-1)){
                cat[i] = cat[i-1]+1;
            }
        }
        //从右到左遍历
        for(int i = n-2;i >=0;i--){
            if(cats_levels.get(i) > cats_levels.get(i+1)){
                cat[i] = Math.max(cat[i],cat[i+1]+1);
            }
        }
        int result = 0;
        //计算总鱼干数
        for(int i = 0;i < n;i++){
            result += cat[i];
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> catsLevels1 = new ArrayList<>();
        catsLevels1.add(1);
        catsLevels1.add(2);
        catsLevels1.add(2);

        List<Integer> catsLevels2 = new ArrayList<>();
        catsLevels2.add(6);
        catsLevels2.add(5);
        catsLevels2.add(4);
        catsLevels2.add(3);
        catsLevels2.add(2);
        catsLevels2.add(16);

        List<Integer> catsLevels3 = new ArrayList<>();
        catsLevels3.add(1);
        catsLevels3.add(2);
        catsLevels3.add(2);
        catsLevels3.add(3);
        catsLevels3.add(3);
        catsLevels3.add(20);
        catsLevels3.add(1);
        catsLevels3.add(2);
        catsLevels3.add(3);
        catsLevels3.add(3);
        catsLevels3.add(2);
        catsLevels3.add(1);
        catsLevels3.add(5);
        catsLevels3.add(6);
        catsLevels3.add(6);
        catsLevels3.add(5);
        catsLevels3.add(5);
        catsLevels3.add(7);
        catsLevels3.add(7);
        catsLevels3.add(4);

        System.out.println(solution(3, catsLevels1) == 4);
        System.out.println(solution(6, catsLevels2) == 17);
        System.out.println(solution(20, catsLevels3) == 35);
    }
}

4.总结

这道题使用贪心算法来解决，其实并不难，需要跟左右两边比较的情况下，我们可以先比较一边，然后再保证前面的比较结果的基础上，比较另外一边，最后统计鱼干数量即可。好了，这道题轻轻松松就AC了，祝大家刷题愉快！

码农公寓