华为OD刷题C卷 - 每日刷题 29（机器人仓库搬砖，爱吃蟠桃的孙悟空）

1、（机器人仓库搬砖）：

这段代码是解决“机器人仓库搬砖”的问题。它提供了一个Java类Main，其中包含main方法和getMinEnergy方法，用于计算机器人每小时充能的最小能量格数，以确保在8小时内搬完所有砖块。

main方法首先读取输入的砖块数量数组，然后调用getMinEnergy方法并打印出所需的最小能量格数。

getMinEnergy方法首先检查仓库数量是否大于8，如果是，则无法完成任务并返回-1。接着，使用二分查找算法来确定每小时所需的最小能量格数。二分查找通过不断缩小搜索范围，逼近每小时最少需要充的能量格数，直到找到满足条件的最小值。

2、（爱吃蟠桃的孙悟空）：

这段代码是解决“爱吃蟠桃的孙悟空”的问题。它提供了一个Java类Main，其中包含main方法和getResult方法，用于计算孙悟空在H小时内吃完所有桃子的最小速度K。

main方法首先读取每颗桃树上的桃子数量数组和守卫离开的时间H，然后调用getResult方法并打印出孙悟空的最小吃桃速度。

getResult方法使用二分查找算法来确定孙悟空的最小吃桃速度。通过遍历桃树数组并计算在当前速度下吃完所有桃子所需的时间，逐步逼近并找到满足条件的最小速度。

package OD353;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @description 机器人仓库搬砖
 * @level 5
 * @score 100
 * @type 二分法
 */
/**
 * 题目描述
 * 机器人搬砖，一共有 N 堆砖存放在 N 个不同的仓库中，第 i 堆砖中有 bricks[i] 块砖头，要求在 8 小时内搬完。
 * <p>
 * 机器人每小时能搬砖的数量取决于有多少能量格，机器人一个小时中只能在一个仓库中搬砖，机器人的能量格只在这一个小时有效，为使得机器人损耗最小化，应尽量减小每次补充的能量格数。
 * <p>
 * 为了保障在 8 小时内能完成搬砖任务，请计算每小时给机器人充能的最小能量格数。
 * <p>
 * 无需考虑机器人补充能力格的耗时；
 * 无需考虑机器人搬砖的耗时；
 * 机器人每小时补充能量格只在这一个小时中有效；
 * 输入描述
 * 第一行为一行数字，空格分隔
 * <p>
 * 输出描述
 * 机器人每小时最少需要充的能量格，若无法完成任务，输出 -1
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //输入一行数字，空格分隔
        int[] bricks = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //8小时内完成，每小时最少补充的能量
        System.out.println(getMinEnergy(bricks));
    }

    //每小时最少补充的能量
    public static int getMinEnergy(int[] bricks) {
        //如果仓库数量大于8，不可能完成任务
        if (bricks.length > 8) {
            return -1;
        }
        //仓库砖的最大值
        int max = Arrays.stream(bricks).max().orElse(0);
        //因为每小时只能在一个仓库，如果仓库数量=8，则必须满足仓库中的最大值，才能完成任务
        if (bricks.length == 8) {
            return max;
        }
        //仓库小于8个，用二分法逐渐逼近最小的能量补充，且补充max时一定能在8小时内完成
        int min = 1;
        int ans = max;
        while (min <= max) {
            int mid = (min + max) / 2;
            //已花费的小时数
            int cost = 0;
            for (int brick : bricks) {
                cost += brick / mid + (brick % mid > 0 ? 1 : 0);
            }
            //如果花费<=8小时，则说明当前mid可以满足，但不一定是最优解
            if (cost <= 8) {
                ans = Math.min(ans, mid);
                max = mid - 1;
            } else {
                //大于等于8，则说明当前补充的能量无法满足
                min = mid + 1;
            }
        }
        return ans;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

package OD354;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @description 爱吃蟠桃的孙悟空
 * @level 5
 * @score 200
 */

/**
 * 题目描述
 * 孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 N 棵桃树，每颗树上都有桃子，守卫将在 H 小时后回来。
 * <p>
 * 孙悟空可以决定他吃蟠桃的速度K（个/小时），每个小时选一颗桃树，并从树上吃掉 K 个，如果树上的桃子少于 K 个，则全部吃掉，并且这一小时剩余的时间里不再吃桃。
 * <p>
 * 孙悟空喜欢慢慢吃，但又想在守卫回来前吃完桃子。
 * <p>
 * 请返回孙悟空可以在 H 小时内吃掉所有桃子的最小速度 K（K为整数）。如果以任何速度都吃不完所有桃子，则返回0。
 * <p>
 * 输入描述
 * 第一行输入为 N 个数字，N 表示桃树的数量，这 N 个数字表示每颗桃树上蟠桃的数量。
 * <p>
 * 第二行输入为一个数字，表示守卫离开的时间 H。
 * <p>
 * 其中数字通过空格分割，N、H为正整数，每颗树上都有蟠桃，且 0 < N < 10000，0 < H < 10000。
 * <p>
 * 输出描述
 * 吃掉所有蟠桃的最小速度 K，无解或输入异常时输出 0。
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //第一行为每颗桃树上的桃子的数量
        int[] peach = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        //H小时内吃完
        int h = sc.nextInt();
        System.out.println(getResult(peach, h));

    }

    //返回孙悟空能在h小时内吃完所有桃子的最小速度
    public static int getResult(int[] peach, int h) {
        int n = peach.length;
        //一个小时最多吃一棵树，多出的时间不能用
        if (n > h) {
            //一定吃不完
            return 0;
        }
        //桃树果子最大值
        int max = Arrays.stream(peach).max().orElse(0);
        //如果刚好数量与h相同，则只能按最大值的速度吃
        if (n == h) {
            return max;
        }
        //h>n 时，用二分法逐渐逼近最小值
        int min = 1;
        //记录结果
        int ans = max;
        while (min <= max) {
            int mid = (min + max) / 2;
            //花费的小时数
            int cost = 0;
            for (int i : peach) {
                cost += i / mid + (i % mid > 0 ? 1 : 0);
            }
            //如果cost<h 则更新，但不一定是最小值
            if (cost <= h) {
                ans = Math.min(ans, mid);
                //往左逼近
                max = mid - 1;
            } else {
                //吃不完 往右逼近
                min = mid + 1;
            }
        }
        return ans;

    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84