题解 | #魔法货车#

题目：
牛妹是鸡蛋商人。由于疫情严重，于是牛妹准备向疫情地区捐赠n个鸡蛋。牛妹请了m辆货车来运送这些鸡蛋，其中第i辆货车能运输x[i]个鸡蛋。因为预料到货车可能装不下所有的鸡蛋，于是牛妹请来了哈利波特·牛，哈利波特·牛使用一次魔法可以来让一辆货车的容量翻倍，牛妹想知道最少需要哈利波特·牛出手几次？

方法一：贪心+差值运算
首先用货物去填充所有货车，并且找到最大容量的货车，如果剩余货物小于0，则不需要施加魔法，直接返回0;否则将容量最大的货车容量翻倍，继续填充货物，如果货物还有剩余，继续在上一次翻倍的基础上翻倍，直到剩余货物为0

图片说明

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) {
        // write code here
        int max=x[0];
        int cnt=0;
        //找到最大容量的货车
        for(int i=0;i<m;i++){
            max=Math.max(max,x[i]);
            n-=x[i];//所有货物减去货车容量
            if(n<=0)return 0;//装得下，直接返回0
        }
        //装不下
        while(n>0){
            n-=max;
            max*=2;//每次让最大货车容量翻倍
            cnt++;
        }
        return cnt;
    }
}

复杂度：
时间复杂度：第一个循环时间复杂度是 $O(m)$ ,第二个循环： $图片说明$ 因此时间复杂度为 $图片说明$
空间复杂度：额外变量的空间为常数级， $O(1)$
方法二：贪心+增值运算
可以直接用排序函数得到货车容量最大值，当货车容量大于等于货物容量时，说明装得下，直接返回0
，如果装不下，每次让最大容量的货车容量翻倍，直到货车容量大于等于货物容量

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) {
        // write code here
        int cnt=0;
        //排序数组，直接得到最大容量的货车
        Arrays.sort(x);
        int max=x[m-1],sum=0;
        for(int i=0;i<m;i++){
           sum+=x[i];
           if(sum>=n)return 0;//货车容量大于等于货物时，装得下，直接返回0
        }
        //装不下
        while(sum<n){
            sum+=max;//货车容量增加
            max*=2;//每次让最大货车容量翻倍
            cnt++;
        }
        return cnt;
    }
}

复杂度：
时间复杂度：第一个循环时间复杂度是O(m),第二个循环： $图片说明$
则第二个循环时间复杂度 $图片说明$ ,加上排序函数的时间复杂度，因此最坏时间复杂度为 $图片说明$
空间复杂度：额外变量的空间为常数级， $O(1)$