当前位置：首页 > news >正文

华为OD机试 - 机器人仓库搬砖 - 二分查找（Python/JS/C/C++ 2024 D卷 100分）

news 2025/4/29 22:25:22

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

机器人搬砖，一共有N堆砖存放在N个不同的仓库中，第 i 堆中有 bricks[i] 块砖头，要求在8小时内搬完。

机器人每小时能搬砖的数量取决于有多少能量格，机器人一个小时中只能在一仓库中搬砖，机器人的能量格每小时补充一次且能量格只在这一个小时有效，为使得机器人损耗最小化，应尽量减小每次补充的能量格数。

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

备注:

无需考虑机器人补充能量的耗时
无需考虑机器人搬砖的耗时
机器人每小时补充能量格只在这一个小时中有效

二、输入描述

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

三、输出描述

输出在8小时内完成搬砖任务，机器人每小时最少需要充多少个能量格；

如果8个小时内无法完成任务，则输出“-1”；

1、输入

30 12 25 8 19

2、输出

四、解题思路

题目关键信息：

机器人一个小时中只能在一仓库中搬砖，机器人的能量格每小时补充一次且能量格只在这一个小时有效。

题目要求：

寻找符合要求的最小能量格数，使其在8小时内能完成工作。

此种场景，二分查找最适合。

五、Python算法源码

def dfs(arr, k):global timessum_value = 0for i in range(len(arr)):times += 1sum_value += arr[i] // kif arr[i] % k != 0:sum_value += 1if sum_value > 8:  # 如果超过8个仓库，无法完成return Falsereturn Trueif __name__ == '__main__':times = 0arr = list(map(int, input().split()))# 如果仓库超过8个，无法在一小时内完成if len(arr) > 8:print(-1)else:# 升序排序arr.sort()total_sum = sum(arr)# 能量格的最小值 = 总数 / 8小时left = total_sum // 8 if total_sum % 8 == 0 else total_sum // 8 + 1print(f"预估最小能量值：{left}")# 能量格的最大值right = arr[-1]min_value = 0# 二分查找while left < right:mid = (left + right) // 2if dfs(arr, mid):  # 能量格多了，减少能量格right = midmin_value = midelse:  # 8小时完不成，增加能量格left = mid + 1print(min_value)print(f"二分查找-循环次数：{times}")

六、JavaScript算法源码

let times = 0;function dfs(arr, k) {let sum = 0;for (let i = 0; i < arr.length; i++) {times++;sum += Math.floor(arr[i] / k);if (arr[i] % k !== 0) {sum++;}if (sum > 8) { // 如果超过8个仓库，无法完成return false;}}return true;
}function main() {const input = prompt("请输入仓库的能量格，用空格分隔：");let arr = input.split(" ").map(Number);// 如果仓库超过8个，无法在一小时内完成if (arr.length > 8) {console.log(-1);return;}// 升序排序arr.sort((a, b) => a - b);let totalSum = arr.reduce((acc, curr) => acc + curr, 0);// 能量格的最小值 = 总数 / 8小时let left = totalSum % 8 === 0 ? totalSum / 8 : Math.floor(totalSum / 8) + 1;console.log("预估最小能量值：" + left);// 能量格的最大值let right = arr[arr.length - 1];let minValue = 0;// 二分查找while (left < right) {let mid = Math.floor((left + right) / 2);if (dfs(arr, mid)) {  // 能量格多了，减少能量格right = mid;minValue = mid;} else {  // 8小时完不成，增加能量格left = mid + 1;}}console.log(minValue);console.log("二分查找-循环次数：" + times);
}// 运行主函数
main();

七、C算法源码

#include <stdio.h>
#include <stdlib.h>int times = 0;// dfs 函数模拟在给定能量格数 k 下，能否在 8 小时内完成任务
int dfs(int arr[], int size, int k) {int sum = 0;for (int i = 0; i < size; i++) {times++;sum += arr[i] / k;if (arr[i] % k != 0) {sum++;}if (sum > 8) {return 0;  // 不能在 8 小时内完成}}return 1;  // 能量格多了，可以完成
}int compare(const void *a, const void *b) {return (*(int *)a - *(int *)b);
}int main() {int n;printf("请输入仓库数量：");scanf("%d", &n);// 如果超过8个仓库，则无法完成if (n > 8) {printf("-1\n");return 0;}int arr[n];printf("请输入每个仓库的能量格（用空格分隔）：");for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}// 升序排序qsort(arr, n, sizeof(int), compare);// 计算总能量格int totalSum = 0;for (int i = 0; i < n; i++) {totalSum += arr[i];}// 能量格的最小值 = 总数 / 8 小时int left = (totalSum % 8 == 0) ? (totalSum / 8) : (totalSum / 8 + 1);printf("预估最小能量值：%d\n", left);// 能量格的最大值int right = arr[n - 1];int min_value = 0;// 二分查找while (left < right) {int mid = (left + right) / 2;if (dfs(arr, n, mid)) {  // 能量格多了，减少能量格right = mid;min_value = mid;} else {  // 8小时完不成，增加能量格left = mid + 1;}}printf("%d\n", min_value);printf("二分查找-循环次数：%d\n", times);return 0;
}

八、C++算法源码

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;int times = 0;// dfs 函数模拟在给定能量格数 k 下，能否在 8 小时内完成任务
bool dfs(const vector<int>& arr, int k) {int sum = 0;for (int i = 0; i < arr.size(); i++) {times++;sum += arr[i] / k;if (arr[i] % k != 0) {sum++;}if (sum > 8) {return false;  // 无法在 8 小时内完成}}return true;  // 能量格多了，可以完成
}int main() {int n;cout << "请输入仓库数量：";cin >> n;// 如果仓库数量大于8，无法在1小时内完成if (n > 8) {cout << -1 << endl;return 0;}vector<int> arr(n);cout << "请输入每个仓库的能量格（用空格分隔）：";for (int i = 0; i < n; i++) {cin >> arr[i];}// 升序排序sort(arr.begin(), arr.end());// 计算总能量格int totalSum = 0;for (int i = 0; i < n; i++) {totalSum += arr[i];}// 能量格的最小值 = 总数 / 8 小时int left = (totalSum % 8 == 0) ? (totalSum / 8) : (totalSum / 8 + 1);cout << "预估最小能量值：" << left << endl;// 能量格的最大值int right = arr[n - 1];int minValue = 0;// 二分查找while (left < right) {int mid = (left + right) / 2;if (dfs(arr, mid)) {  // 能量格多了，减少能量格right = mid;minValue = mid;} else {  // 8 小时完不成，增加能量格left = mid + 1;}}cout << minValue << endl;cout << "二分查找-循环次数：" << times << endl;return 0;
}