阅读量:5
从2024年4月15号开始，OD机考全部配置为2024D卷。
注意两个关键点：
- 会遇到C卷复用题。虽然可能存在幸存者偏差，但肯定还会有一大部分的旧题。
- 现在又支持做完题目之后倒回去改了。就是可以先做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了解更多
