题解 | #魔法货车#

题意整理

有m辆货车，每辆货车能运送若干个鸡蛋。
总共要运送n个鸡蛋。
如果货车装不下，可以使用魔法将某辆货车容量翻倍，问最少需要使用多少次魔法，才能一次运完所有鸡蛋。

方法一（排序+贪心）

1.解题思路

首先对x数组进行排序，获得容量最大的货车。然后计算还剩多少鸡蛋运不走，每次选择容量最大的货车施加魔法，剩下的鸡蛋就会最大程度地减少，当没有鸡蛋剩下时，就不用施加魔法了。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x int整型一维数组 
     * @return int整型
     */
    public int Holy (int n, int m, int[] x) {
        //排序
        Arrays.sort(x);
        //获取最大值
        int max=x[m-1];

        //看还剩下多少鸡蛋运不走
        for(int i=0;i<m;i++){
            n-=x[i];
        }

        int cnt=0;
        while(n>0){
            //每使用一次魔法，就会多运走max*(1<<cnt)的鸡蛋
            n-=max*(1<<cnt);
            cnt++;
        }
        return cnt;
    }
}

3.复杂度分析

时间复杂度：假设剩下的鸡蛋数为m，货车的最大容量为max，那么总共需要施加 $图片说明$ 次魔法，时间复杂度是 $图片说明$ ，如果算上排序，则时间复杂度是 $O(mlog_2m)$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度是 $O(1)$ 。

方法二（贪心）

1.解题思路

首先遍历x数组，计算所有货车总容量sum以及最大货车容量max，当sum小于n时，说明有鸡蛋运不走，需要施加魔法。每次选择容量最大的货车施加魔法，每使用一次魔法，就会多运走 $max*(1<<cnt)$ 的鸡蛋

动图展示：
图片说明

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x int整型一维数组 
     * @return int整型
     */
    public int Holy (int n, int m, int[] x) {
        //遍历数组，计算最大值以及累加和
        int max=-1,sum=0;
        for(int i=0;i<m;i++){
            max=Math.max(x[i],max);
            sum+=x[i];
        }

        int cnt=0;
        //如果所有货车容量之和小于n，则施加魔法
        while(sum<n){
            //每使用一次魔法，就会多运走max*(1<<cnt)的鸡蛋
            sum+=max*(1<<cnt);
            cnt++;
        }
        return cnt;
    }
}

3.复杂度分析

时间复杂度：假设所有货车容量总和为sum，货车的最大容量为max，需要运走n个鸡蛋，那么总共需要施加 $图片说明$ 次魔法，施加魔法前，需要遍历x数组，所以时间复杂度是 $图片说明$ 。
空间复杂度：需要额外常数级别的空间，所以空间复杂度是 $O(1)$ 。