题解 | #魔法货车#

思路：

题目的主要信息：

• 一共辆货车，每辆容量为，需要运送n个鸡蛋
• 如果装满货车后，还剩有鸡蛋，则选择一辆货车容量翻倍，继续装，如此循环
• 同一辆车可以多次翻倍，求需要翻倍多少次

方法一：贪心+排序+差值运算
具体做法：
使用sort函数对数组排序，找到最大值。遍历数组x，对于每个，用减去容量，如果剩余鸡蛋数小于等于0，则不需要魔法返回0.如果最后还是大于0，我们选择增大容量最大的车，直到小于等于0.

class Solution {
public:
    int Holy(int n, int m, vector<int>& x) {
        int res = 0;
        sort(x.begin(), x.end());
        int maxx = x[m - 1]; //找到容量最大的车
        for(int i = 0; i < m; i++){
            if(x[i] > n)
                return 0;
            n -= x[i];
        }
        while(n > 0){
            n -= maxx; //每次选最大容量的车增加，增加数量为加倍前的容量 
            maxx *= 2;
            res++;
        }
        return res;
    }
};

复杂度分析：

• 时间复杂度：，sort函数排序，遍历一次x数组，最坏情况（)第二个循环相当于是差值的对数运算
• 空间复杂度：，常数空间

方法二：贪心+增加计算
具体做法：
利用贪心思想，每次首先将所有的车直接装满的到所有车的容量，并在这时找到最大值。如果我们每次增加的是最大容量的车，直到能够达到。

C++版本

class Solution {
public:
    int Holy(int n, int m, vector<int>& x) {
        int maxx = 0;
        int res = 0;
        int sum = 0;
        for(int i = 0; i < m; i++){ 
            sum += x[i]; //求这些货车能装多少
            maxx = max(maxx, x[i]); //找到容量最大的车
        }
        while(sum < n){
            sum += maxx; //每次选最大容量的车增加，增加数量为加倍前的容量 
            maxx *= 2;
            res++;
        }
        return res;
    }
};

Python版本

class Solution:
    def Holy(self , n , m , x ):
        maxx = 0
        res = 0
        sumx = 0
        for i in range(m):
            sumx += x[i] #求这些货车能装多少
            maxx = max(maxx, x[i]) #找到容量最大的车
        while sumx < n :
            sumx += maxx #每次选最大容量的车增加，增加数量为加倍前的容量
            maxx *= 2;
            res += 1;
        return res;

复杂度分析：

• 时间复杂度：，一次遍历，最坏情况（)第二个循环相当于是差值的对数运算
• 空间复杂度：，常数空间