首页 > 试题广场 >

魔法货车

[编程题]魔法货车

热度指数：1536 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

示例1

输入

4,1,[2]

输出

说明

哈利波特·牛出手一次即可

备注:

一辆车可被多次施加魔法

算法知识视频讲解

C/C++

nbgao

class Solution {
public:

    int Holy(int n, int m, vector<int>& x) {
        long s=0;
        int cnt=0;
        for(int i=0;i<m;i++)
            s += x[i];
        sort(x.begin(), x.end());
        while(s<n){
            cnt++;
            s += x[m-1];
            x[m-1] <<= 1;
        }
        return cnt;
    }
};

发表于 2020-06-21 13:16:57 回复(0)

FrankKong

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 maxV = 0;
        long long sum = 0;
        for(int i = 0; i < m; i++){
            sum += x[i];
            maxV = max(maxV, x[i]);
        }
        int count = 0;
        while(sum < n){
            sum += maxV;
            maxV *= 2;
            count++;
        }
        return count;
    }
};

一直选最大的

发表于 2020-11-09 14:11:30 回复(0)

Resolmi

public int Holy (int n, int m, int[] x) {
    // write code here
    Arrays.sort(x);
    int sum = 0;
    for (int i = m-1; i >= 0; i--){
        sum += x[i];
        if (sum >= n) {
            return 0;
        }
    }
    int xm = x[m-1];
    int res = 0;
    while(sum < n){
        sum += xm;
        xm<<=1;
        res++;
    }
    return res;
}

发表于 2020-08-31 18:47:38 回复(0)

请叫我算术嘉

package NowcodeHuaWei;

import java.util.Arrays;

public class Solution {

    public int Holy (int n, int m, int[] x) {
        // write code here
        int magic = 0;
        while(total(x) < n){
            int i = maxIndex(x);
            if(x[i] > n){
                return 0;
            }
            x[i] *= 2;
            magic += 1;
        }

        return magic;
    }
    public static int maxIndex(int[] x){
        int max=x[0],min=x[0];
        int maxId = 0;
        for(int i=1;i<x.length;i++){
            if(max<x[i]){
                max=x[i];
                maxId=i;
            }
        }
        return maxId;
    }

    public static int total(int[] x){
        int sum = 0;
        for(int  i = 0;i < x.length;i++){
            sum += x[i];
        }

        return sum;
    }
}

编辑于 2020-08-23 19:44:53 回复(0)

Python

牛客577127890号

一直给最大的就行

#
# 
# @param n int整型 
# @param m int整型 
# @param x int整型一维数组 
# @return int整型
#
class Solution:
    def Holy(self , n , m , x ):
        magic = 0
        while sum(x) < n:
            m1 = max(x)
            i = x.index(m1)
            x[i] *= 2
            magic += 1
        return magic
        # write code here

发表于 2020-08-11 15:24:50 回复(0)

太咸了

python自己写输入输出才能过，用给的类和函数写超时

发表于 2020-07-13 17:30:04 回复(0)

繁星似尘

需要处理一下数据溢出的情况。

int Holy(int n, int m, vector<int>& x) {
        int maxNum = 0;
        for(int i=0;i<m;i++){
            if(x[i] > n){ //处理溢出
                return 0;
            }
            n -= x[i];
            maxNum = max(maxNum,x[i]);
        }
        int res = 0;
        while(n > 0){
            n -= maxNum;
            res++;
            maxNum *= 2;
        }
        return res;
    }

编辑于 2020-06-19 19:46:22 回复(3)