从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()))# 设置搬砖时间上限为8hh = 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小时内搬完所有砖# 直接输出-1if 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()))# 设置搬砖时间上限为8hh = 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小时内搬完所有砖# 直接输出-1if 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了解更多