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

╰半夏微凉° 2024-04-17 10:29 29阅读 0赞

![在这里插入图片描述][986dcebce006483fb6846cb29a3928a7.gif_pic_center]

> 华为OD机试 2024C卷题库疯狂收录中，刷题[**点这里**][Link 1]

### 专栏导读 ###

本专栏收录于[《华为OD机试（JAVA）真题（A卷+B卷+C卷）》][OD_JAVA_A_B_C]。

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

### 一、题目描述 ###

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

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

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

备注:

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

### 二、输入描述 ###

程序有输入为“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;
                    }
                }
            }
        }
    }

![在这里插入图片描述][6019c28865b042f594b2aa217e9466d4.bmp_pic_center]

#### 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;
        }
    }

![在这里插入图片描述][6837fc84aac2457b8a9e15f4df9a7ba2.bmp_pic_center]

### 六、效果展示 ###

#### 1、输入 ####

10 13 17 19 29

#### 2、输出 ####

#### 3、说明 ####

1.  预估最小能量值left=总数/8小时 = 11
2.  right = 仓库所需最大能量格29
3.  mid = (left+rifht)/2 = 20
4.  如果每次补充的能量格数为20，则5小时完成，补充的能量太多了；
5.  left = 11，right = 20，mid = (left+rifht)/2 = 15
6.  如果每次补充的能量格数为15，则8小时完成
7.  减少能量值，看看能不能完成left = 11，right = 15，mid = (left+rifht)/2 = 13
8.  循环往复，二分查找

![在这里插入图片描述][1d4cd1bd4ede492aac45f1923013d084.bmp_pic_center]

?下一篇：[华为OD机试 - 简易内存池 - 逻辑分析（Java 2024 C卷 200分）][OD_ - _ - _Java 2024 C_ 200]

?本文收录于，[华为OD机试（JAVA）真题（A卷+B卷+C卷）][OD_JAVA_A_B_C]

**刷的越多，抽中的概率越大**，每一题都有详细的答题思路、详细的代码注释、样例测试，发现新题目，随时更新，全天CSDN在线答疑。

![在这里插入图片描述][8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]

[986dcebce006483fb6846cb29a3928a7.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/c33e968e50dd4cb98672a2ec06a93d40.gif
[Link 1]: https://blog.csdn.net/guorui_java/article/details/132683473
[OD_JAVA_A_B_C]: https://blog.csdn.net/guorui_java/category_12293298.html
[6019c28865b042f594b2aa217e9466d4.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/6019c28865b042f594b2aa217e9466d4.bmp#pic_center
[6837fc84aac2457b8a9e15f4df9a7ba2.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/6837fc84aac2457b8a9e15f4df9a7ba2.bmp#pic_center
[1d4cd1bd4ede492aac45f1923013d084.bmp_pic_center]: https://img-blog.csdnimg.cn/direct/1d4cd1bd4ede492aac45f1923013d084.bmp#pic_center
[OD_ - _ - _Java 2024 C_ 200]: https://blog.csdn.net/guorui_java/article/details/132197477
[8dbe8dd8723c4636af5926ccf1c511b0.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/45cb1f93b829434f984c19b157286691.gif