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

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

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

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

文章目录

题目描述与示例题目描述输入描述输出描述示例输入输出说明

解题思路代码解法一：左闭右开写法pythonjavacpp

解法二：左闭右闭写法pythonjavacpp

时空复杂度

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

题目描述与示例

题目描述

机器人搬砖，一共有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

#include

#include

#include

using namespace std;

// 计算花费在速度k的条件下，所花费的时间h的函数

int calHourUsed(vector& nums, int k) {

int hours = 0;

for (int p : nums) {

hours += ceil((double)p / k);

}

return hours;

}

// 二分查找求解问题的函数

int minEatingSpeed(vector& 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 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

#include

#include

#include

using namespace std;

// 计算花费在速度k的条件下，所花费的时间h的函数

int calHourUsed(vector& nums, int k) {

int hours = 0;

for (int p : nums) {

hours += ceil((double)p / k);

}

return hours;

}

// 二分查找求解问题的函数

int minEatingSpeed(vector& 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 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了解更多

好文推荐

 您阅读本篇文章共花了：