OD_2024_C卷_200分_1、爱吃蟠桃的孙悟空【JAVA】【二分法】

老板们如果有更好的方案请回帖一下、探讨一下 谢谢

题目：

孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 N 棵桃树，每颗树上都有桃子，守卫将在 H 小时后回来。
孙悟空可以决定他吃蟠桃的速度K（个/小时），每个小时选一颗桃树，并从树上吃掉 K 个，如果树上的桃子少于 K 个，则全部吃掉，并且这一小时剩余的时间里不再吃桃。
孙悟空喜欢慢慢吃，但又想在守卫回来前吃完桃子。
请返回孙悟空可以在 H 小时内吃掉所有桃子的最小速度 K（K为整数）。如果以任何速度都吃不完所有桃子，则返回0。

输入描述：

第一行输入为 N 个数字，N 表示桃树的数量，这 N 个
第二行输入为一个数字，表示守卫离开的时间 H。
其中数字通过空格分割，N、H为正整数，每颗树上都有蟠桃，且 0 < N < 10000，0 < H < 10000。

输出描述

吃掉所有蟠桃的最小速度 K，无解或输入异常时输出 0

示例

示例1：

输入：2 3 4 5
      4
结果：5
1
2
3

示例2：

输入：2 3 4 5
     3
结果：0
1
2
3

示例3：

输入：30 11 23 4 20
      6
结果：23
1
2
3

---

代码-java

package odjava;

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

/**
 * 爱吃蟠桃的孙悟空-二分法
 */
public class 爱吃蟠桃的孙悟空 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int[] peachTrees = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int hours = Integer.parseInt(scanner.nextLine());

        System.out.println(getOptimalSpeed(peachTrees, hours));
    }

    public static int getOptimalSpeed(int[] peachTrees, int hours) {
        // 桃树数量
        int treeCount = peachTrees.length;

        // 如果桃树数量大于等于小时数，则一小时吃一颗即可
        if (treeCount >= hours) {
            return Arrays.stream(peachTrees).max().orElse(0);
        }

        // 最小吃桃速度为1
        int minSpeed = 1;

        // 最大吃桃速度为桃树中最多的桃子数
        int maxSpeed = Arrays.stream(peachTrees).max().orElse(0);

        int optimalSpeed = maxSpeed;

        // 使用二分法查找最优吃桃速度
        while (minSpeed <= maxSpeed) {
            int midSpeed = (minSpeed + maxSpeed) / 2;

            // 如果以当前速度可以在规定时间内吃完所有桃子，则更新最优速度为当前速度，并缩小搜索范围
            if (canEatInTime(midSpeed, hours, peachTrees)) {
                optimalSpeed = midSpeed;
                maxSpeed = midSpeed - 1;
            } else {
                // 否则增大速度继续搜索
                minSpeed = midSpeed + 1;
            }
        }

        return optimalSpeed;
    }

    // 检查以给定速度是否能在规定时间内吃完所有桃子
    public static boolean canEatInTime(int speed, int limit, int[] peachTrees) {
        int timeTaken = 0;

        for (int peachCount : peachTrees) {
            // 吃完一颗桃子所需时间
            int timeForPeach = (int) Math.ceil((double) peachCount / speed);
            timeTaken += timeForPeach;

            // 如果已花费时间超过规定时间限制，则无法以当前速度在规定时间内吃完所有桃子
            if (timeTaken > limit) {
                return false;
            }
        }

        return true;
    }
}

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