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

华为OD机试 - 机器人仓库搬砖 - 二分查找（Java 2024 E卷 100分）

news 2025/4/29 17:40:46

在这里插入图片描述

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

专栏导读

本专栏收录于《华为OD机试（JAVA）真题（E卷+D卷+A卷+B卷+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小时内能完成工作。

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

五、Java算法源码

1、深度优先搜索，搜索最少需要充多少个能量格

从可能的最小能量值开始递归搜索，搜索最少能量格。

public class Test00 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();Arrays.sort(arr);int sum = 0;for (int i = 0; i < arr.length; i++) {sum += arr[i];}int k = sum % 8 == 0 ? sum / 8 : sum / 8 + 1;System.out.println(k);dfs(arr, k);System.out.println("递归-循环次数："+times);}static boolean flag = false;static int times = 0;private static void dfs(int[] arr, int k) {if (flag) {return;}int sum = 0;for (int i = 0; i < arr.length; i++) {times++;sum += arr[i] / k;if (arr[i] % k != 0) {sum++;}if (sum > 8) {dfs(arr, ++k);} else {if (i == arr.length - 1) {System.out.println(k);flag = true;}}}}
}

在这里插入图片描述

2、二分查找

二分查找相当于折半搜索，效率更高。

public class Test01 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int[] arr = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();// 能量格只在这一个小时有效，如果大于8个仓库，每小时只能完成一个，所以肯定完不成if(arr.length > 8){System.out.println(-1);return;}// 升序排序Arrays.sort(arr);int sum = 0;for (int i = 0; i < arr.length; i++) {sum += arr[i];}// 能量格的最小值 = 总数/8小时int left = sum % 8 == 0 ? sum / 8 : sum / 8 + 1;System.out.println("预估最小能量值："+left);// 能量格的最大值int right = arr[arr.length - 1];// 最小能量格数int min = 0;// 二分查找while (left < right) {int mid = (left + right) / 2;if (dfs(arr, mid)) {// 能量格多了，减少能量格，二分低左侧right = mid;min = mid;} else {// 8小时完不成。能量格少了，增加能量格，二分高右侧left = mid + 1;}}System.out.println(min);System.out.println("二分查找-循环次数：" + times);}static int times = 0;private static boolean dfs(int[] arr, int k) {int sum = 0;for (int i = 0; i < arr.length; i++) {times++;sum += arr[i] / k;if (arr[i] % k != 0) {sum++;}if (sum > 8) {// 8小时完不成。能量格少了return false;}}// 能量格多了return true;}
}