NC555 题解 | #魔法货车#

题意分析

• 给出m个货车，每个货车可以装的鸡蛋的数量。显然，我们需要装n个鸡蛋。同时我们可以执行魔法操作，将某一辆车装载的鸡蛋的数量加倍。问最少执行多少次魔法操作可以使我们装完所有的鸡蛋。

思路分析

• 一个很简单的题目，我们需要做的就是如果装不下，那么就将初始装载最多的那个货车装载的鸡蛋的数量加倍。直到可以装下为止。

• 如下图

• 代码分为两种写法，Go和C++
  • 我们需要将拆分成$mx\ast 2^x=n，x=lo{g}_2\left(n/mx\right)mx*2^x=n，x=log\_2(n/mx)$mx∗2x=n，x=log2​(n/mx),所以最坏的时间复杂度为$O\left(lo{g}_{2}n\right)O(log\_2n)$O(log2​n)
  • 过程中只用了少数几个变量进行计算，空间复杂度为$O\left(1\right)O(1)$O(1)

写法一 C++

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param m int整型 
     * @param x int整型vector 
     * @return int整型
     */
    int Holy(int n, int m, vector<int>& x) {
        // write code here
        int sum=0;
        int mx=0;
        // 记录下数组的最大值
        for(auto y:x){
            sum+=y;
            mx=max(mx,y);
        }
        
        int ans=0;
        // 循环让装载鸡蛋最多的货车加倍即可
        while(sum<n){
            ans++;
            sum+=mx;
            mx=mx+mx;
        }
        return ans;
    }
};

写法二 Go

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @param m int整型 
 * @param x int整型一维数组 
 * @return int整型
*/
func Holy( n int ,  m int ,  x []int ) int {
    // write code here
    sum := 0
    mx := 0
    // 找到运输鸡蛋最多的货车的运输数量，同时记录下初始的所有的总和
    for i := 0; i < m; i++ {
        if(mx<x[i]){
            mx=x[i]
        }
        sum += x[i]
    }
    
    ans := 0
    for {
        // 如果当前总和满足装载全部鸡蛋，那么退出
        if(sum>=n){
            break
        }
        ans++
        sum+=mx
        // 装载最多的进行加倍即可
        mx += mx
    }
    
    return ans
}