魔法货车

题意:
有辆货车,每辆货车容量为,现在需要运送个鸡蛋,如果每个货车装满后还有鸡蛋则选择一辆货车进行容量翻倍,然后继续装鸡蛋直到鸡蛋装完为止.

案例
输入：4,1,[2]
返回值：1
案例说明： 只需要将2翻倍一次即可

方法一 贪心 + 增值计算

首先需要统计现有的货车的总容量是否大于等于n,如果有则不需要进行货车改变.但现有的容量小于鸡蛋数量,则最优的方式是改变最大的货车容量，所以对于总容量小于n时每次将最大容量的货车容量翻倍直到大于鸡蛋数量n即可

class Solution {
public:
    int Holy(int n, int m, vector<int>& x) {
        // write code here
        int cont = 0, mx = 0, ans = 0;
        for(int i = 0; i < m; i ++) cont += x[i], mx = max(mx, x[i]); //统计所有货车的总量, 并取最大值
        while(cont < n) cont += mx, mx *= 2, ans ++; //不断扩大最大值的货车直到达到鸡蛋总数以上
        return ans;
    }
};

时间复杂度: 遍历一次数组,并且不断扩大最大车厢容量
空间复杂度: 使用若干个记录元素

方法二 贪心 + 减值计算

想法与方法一一致，但在每次统计货车容量时将鸡蛋数量减去货车容量,最后如果鸡蛋的数量小于等于0则说明不需要增加货车容量,如果鸡蛋数量n还是大于0则每次扩大最大货车容量并把鸡蛋数量n减去增加的容量直到n小于等于0

class Solution {
public:
    int Holy(int n, int m, vector<int>& x) {
        // write code here
        int mx = 0, ans = 0;
        for(int i = 0; i < m; i ++) n -= x[i], mx = max(mx, x[i]); //将货车的总量减少鸡蛋的总数,并不断取最大值
        while(n > 0) n -= mx, mx *= 2, ans ++; //不断扩大最大值的货车并将扩大值减少鸡蛋数量
        return ans;
    }
};

时间复杂度: 遍历一次数组,并且不断扩大最大车厢容量
空间复杂度: 使用若干个记录元素