【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【二分查找】2024D-机器人搬砖【欧弟算法】全网注释最详细分类最全的华为OD真题题解

文章【Py/Java/C++三种语言OD独家2024D卷真题】20天拿下华为OD笔试之【二分查找】2024D-机器人搬砖【欧弟算法】全网注释最详细分类最全的华为OD真题题解分享给大家，欢迎收藏Java资料网，专注分享技术知识

从2024年4月15号开始，OD机考全部配置为2024D卷。
注意两个关键点：

1. 会遇到C卷复用题。虽然可能存在幸存者偏差，但肯定还会有一大部分的旧题。
2. 现在又支持做完题目之后倒回去改了。就是可以先做200的再做100的，然后可以反复提交。

有LeetCode算法/华为OD考试扣扣交流群可加 948025485
可上全网独家的 欧弟OJ系统 练习华子OD、大厂真题
绿色聊天软件戳 od1336了解算法冲刺训练

题目描述与示例

题目描述

机器人搬砖，一共有N堆砖存放在N个不同的仓库中，第i堆砖中有bricks[i]块砖头，要求在8小时内搬完。机器人每小时能搬砖的数量取决于有多少能量格，机器人一个小时中只能在一个仓库中搬砖，机器人的能量格每小时补充一次且能量格只在这一个小时有效，为使得机器人损耗最小化，尽量减小每次补充的能量格数。

为了保障在8小时内能完成搬砖任务，请计算每小时给机器人充能的最小能量格数。

备注:

1、无需考虑机器人补充能量格的耗时

2、无需考虑机器人搬砖的耗时

3、机器人每小时补充能量格只在这一个小时中有效。

输入描述

程序输入为"30 12 25 8 19"一个整数数组，数组中的每个数字代表第i堆砖的个数，每堆砖的个数不超过100

输出描述

输出在8小时内完成搬砖任务，机器人每小时最少需要充多少个能量格；如果8个小时内无论如何都完成不了任务，则输出"-1"

示例

输入

30 12 25 8 19

输出

15

说明

解题思路

注意，本题和LeetCode875.爱吃香蕉的珂珂、【二分查找】2023C-孙悟空吃蟠桃几乎完全一致。甚至更加简单，因为时间固定为8

代码

解法一：左闭右开写法

python

# 题目：【二分查找】2023C-机器人搬砖
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：二分查找
# 代码看不懂的地方，请直接在群上提问
# 相关题目：LeetCode875.爱吃香蕉的珂珂


# 导入向上取整函数ceil，用于后续的计算
from math import ceil


# 输入每一个仓库的砖块数目
nums = list(map(int, input().split()))
# 设置搬砖时间上限为8h
h = 8

# 计算花费在速度k的条件下，所花费的时间h的函数
def cal_hour_used(nums, k):
    return sum(ceil(p / k) for p in nums)


# 二分查找求解问题的函数
def minEatingSpeed(nums, h):
    # 左闭右开区间，right取最大的那一堆的值再+1
    left, right = 1, max(nums) + 1
    # left和right相等时，区间消失，退出循环
    while left < right:
        mid = (left + right) // 2
        # 花费时间太少，速度偏大，速度还可以减小，
        # 搜索区间向左折半，right可以向左移动
        if cal_hour_used(nums, mid) <= h:
            right = mid
        else:
            left = mid + 1
    # 退出循环时，left和right是恰好满足条件cal_hour_used(nums, mid) <= h的速度
    # 返回left或right均可
    return left


# 如果nums的长度已经大于h，一定无法在h小时内搬完所有砖
# 直接输出-1
if len(nums) > h:
    print(-1)
# 否则进行二分，输出答案
else:
    print(minEatingSpeed(nums, h))

java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        int h = 8;
        if (nums.length > h){
            System.out.println(-1);
        } else {
            int result = minEatingSpeed(nums, h);
            System.out.println(result);  
        }

    }

    // 计算花费在速度k的条件下，所花费的时间h的函数
    public static int calHourUsed(int[] nums, int k) {
        int hours = 0;
        for (int p : nums) {
            hours += Math.ceil((double) p / k);
        }
        return hours;
    }

    // 二分查找求解问题的函数
    public static int minEatingSpeed(int[] nums, int h) {
        // 左闭右开区间，right取最大的那一堆的值再+1
        int left = 1, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        right += 1;
        // left和right相等时，区间消失，退出循环
        while (left < right) {
            // 花费时间太少，速度偏大，速度还可以减小，
            // 搜索区间向左折半，right可以向左移动
            int mid = left + (right - left) / 2;
            if (calHourUsed(nums, mid) <= h) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        // 退出循环时，left和right是恰好满足条件cal_hour_used(nums, mid) <= h的速度
        // 返回left或right均可
        return left;
    }
}

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>

using namespace std;

// 计算花费在速度k的条件下，所花费的时间h的函数
int calHourUsed(vector<int>& nums, int k) {
    int hours = 0;
    for (int p : nums) {
        hours += ceil((double)p / k);
    }
    return hours;
}

// 二分查找求解问题的函数
int minEatingSpeed(vector<int>& nums, int h) {
    // 左闭右开区间，right取最大的那一堆的值再+1
    int left = 1, right = 0;
    for (int num : nums) {
        right = max(right, num);
    }
    right += 1;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (calHourUsed(nums, mid) <= h) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    // 退出循环时，left和right是恰好满足条件cal_hour_used(nums, mid) <= h的速度
    // 返回left或right均可
    return left;
}

int main() {
    vector<int> nums;
    string input;
    getline(cin, input);
    istringstream iss(input);
    int num;
    while (iss >> num) {
        nums.push_back(num);
    }
    int h = 8;
    if (nums.size() > h){
        cout << -1 << endl;
    } else {
        int result = minEatingSpeed(nums, h);
        cout << result << endl;
    }
    return 0;
}

解法二：左闭右闭写法

python

# 题目：【二分查找】2023C-机器人搬砖
# 分值：100
# 作者：许老师-闭着眼睛学数理化
# 算法：二分查找
# 代码看不懂的地方，请直接在群上提问
# 相关题目：LeetCode875.爱吃香蕉的珂珂


# 导入向上取整函数ceil，用于后续的计算
from math import ceil


# 输入每一个仓库的砖块数目
nums = list(map(int, input().split()))
# 设置搬砖时间上限为8h
h = 8

# 计算花费在速度k的条件下，所花费的时间h的函数
def cal_hour_used(nums, k):
    return sum(ceil(p / k) for p in nums)


# 二分查找求解问题的函数
def minEatingSpeed(nums, h):
    # 左闭右闭区间，right取最大的那一堆的值
    left, right = 1, max(nums)
    # left严格大于right时，区间消失，退出循环
    while left <= right:
        mid = (left + right) // 2
        # 花费时间太少，速度偏大，速度还可以减小，
        # 搜索区间向左折半，right可以向左移动
        if cal_hour_used(nums, mid) <= h:
            right = mid - 1
        else:
            left = mid + 1
    # 退出循环时，存在left = right+1
    # left是恰好满足条件cal_hour_used(nums, mid) <= h的速度
    # right是恰好满足条件cal_hour_used(nums, mid) > h的速度
    # 返回left或right+1均可
    return left


# 如果nums的长度已经大于h，一定无法在h小时内搬完所有砖
# 直接输出-1
if len(nums) > h:
    print(-1)
# 否则进行二分，输出答案
else:
    print(minEatingSpeed(nums, h))

java

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] input = scanner.nextLine().split(" ");
        int[] nums = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            nums[i] = Integer.parseInt(input[i]);
        }
        int h = 8;
        if (nums.length > h){
            System.out.println(-1);
        } else {
            int result = minEatingSpeed(nums, h);
            System.out.println(result);  
        }
    }

    // 计算花费在速度k的条件下，所花费的时间h的函数
    public static int calHourUsed(int[] nums, int k) {
        int hours = 0;
        for (int p : nums) {
            hours += Math.ceil((double) p / k);
        }
        return hours;
    }

    // 二分查找求解问题的函数
    public static int minEatingSpeed(int[] nums, int h) {
        // 左闭右闭区间，right取最大的那一堆的值
        int left = 1, right = 0;
        for (int num : nums) {
            right = Math.max(right, num);
        }
        while (left <= right) {
            int mid = left + (right - left) / 2;
            // 花费时间太少，速度偏大，速度还可以减小，
            // 搜索区间向左折半，right可以向左移动
            if (calHourUsed(nums, mid) <= h) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // 退出循环时，存在left = right+1
        // left是恰好满足条件calHourUsed(nums, mid) <= h的速度
        // right是恰好满足条件calHourUsed(nums, mid) > h的速度
        // 返回left或right+1均可
        return left;
    }
}

cpp

#include <iostream>
#include <vector>
#include <cmath>
#include <sstream>

using namespace std;

// 计算花费在速度k的条件下，所花费的时间h的函数
int calHourUsed(vector<int>& nums, int k) {
    int hours = 0;
    for (int p : nums) {
        hours += ceil((double)p / k);
    }
    return hours;
}

// 二分查找求解问题的函数
int minEatingSpeed(vector<int>& nums, int h) {
    // 左闭右闭区间，right取最大的那一堆的值
    int left = 1, right = 0;
    for (int num : nums) {
        right = max(right, num);
    }
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // 花费时间太少，速度偏大，速度还可以减小，
        // 搜索区间向左折半，right可以向左移动
        if (calHourUsed(nums, mid) <= h) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // 退出循环时，存在left = right+1
    // left是恰好满足条件calHourUsed(nums, mid) <= h的速度
    // right是恰好满足条件calHourUsed(nums, mid) > h的速度
    // 返回left或right+1均可
    return left;
}

int main() {
    vector<int> nums;
    string input;
    getline(cin, input);
    istringstream iss(input);
    int num;
    while (iss >> num) {
        nums.push_back(num);
    }
    int h = 8;
    if (nums.size() > h){
        cout << -1 << endl;
    } else {
        int result = minEatingSpeed(nums, h);
        cout << result << endl;
    }
    return 0;
}

时空复杂度

• 时间复杂度：O(NlogN)。其中N为nums数组长度。
• 空间复杂度：O(1)。

---

华为OD算法/大厂面试高频题算法练习冲刺训练

• 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名！目前已服务300+同学成功上岸！

• 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

• 每期人数维持在20人内，保证能够最大限度地满足到每一个同学的需求，达到和1v1同样的学习效果！

• 60+天陪伴式学习，40+直播课时，300+动画图解视频，300+LeetCode经典题，200+华为OD真题/大厂真题，还有简历修改、模拟面试、专属HR对接将为你解锁

• 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

• 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

• 绿色聊天软件戳 od1336了解更多

文章来源:https://blog.csdn.net/weixin_48157259/article/details/137877689
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！