孙悟空吃蟠桃【华为OD机试JAVA&Python&C++&JS题解】

一. 题目-孙悟空吃蟠桃

孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有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
说明：

示例2

输入：

2 3 4 5
3
输出：

0
说明：

示例3

输入：

30 11 23 4 20
6
输出：

23

二.解题思路

当解决这个问题时，我们可以采用二分查找的方法来找到孙悟空吃蟠桃的最小速度K。具体的思路如下：

1. 确定搜索范围： 最小速度K的范围在1到桃树中最多桃子的数量之间，因为速度不可能小于1，也不可能大于任何一颗树上的桃子数量。

2. 使用二分查找： 在确定了搜索范围之后，我们可以使用二分查找来缩小速度K的范围。对于每个中间值，我们检查是否能够在规定的时间内吃完所有桃子。如果可以，说明速度K可能太大，我们在左半部分继续查找；否则，说明速度K太小，我们在右半部分继续查找。

3. 检查吃完所有桃子的条件： 对于给定的速度K，我们需要检查孙悟空是否能够在规定的时间内吃完所有桃子。我们遍历每棵树，计算吃掉每颗树上桃子所需的时间，然后判断总时间是否小于等于规定的时间H。

4. 返回结果： 最终，我们找到的速度K即为孙悟空吃蟠桃的最小速度，或者如果无解则返回0。

这样的算法复杂度较低，是一种高效的解决方案。

三.题解代码

Python题解代码

def min_speed(N, H):
    total_peaches = sum(N)
    left, right = 1, total_peaches
    min_speed = 0
 
    while left <= right:
        mid = (left + right) // 2
        time_needed = sum((p - 1) // mid + 1 for p in N)
 
        if time_needed <= H:
            min_speed = mid
            right = mid - 1
        else:
            left = mid + 1
 
    return min_speed
 
input_str = input()
N = list(map(int, input_str.split()))
H = int(input())
 
print(min_speed(N, H))

JAVA题解代码

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int h = sc.nextInt();
        int[] peaches = new int[n];
        for (int i = 0; i < n; i++) {
            peaches[i] = sc.nextInt();
        }
        System.out.println(minSpeed(peaches, h));
    }
 
    public static int minSpeed(int[] peaches, int h) {
        int totalPeaches = 0;
        for (int p : peaches) {
            totalPeaches += p;
        }
        int left = 1;
        int right = totalPeaches;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canFinish(peaches, mid, h)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return canFinish(peaches, left, h) ? left : 0;
    }
 
    public static boolean canFinish(int[] peaches, int speed, int h) {
        int time = 0;
        for (int p : peaches) {
            time += (p + speed - 1) / speed;
        }
        return time <= h;
    }
}

C/C++题解代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    vector<int> peaches;
    int n, h;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        peaches.push_back(num);
    }
    cin >> h;
 
    int left = 1, right = 1e9;
    int ans = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        int time = 0;
        for (int i = 0; i < n; i++) {
            time += (peaches[i] + mid - 1) / mid;
        }
        if (time <= h) {
            ans = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    cout << ans << endl;
    return 0;
}

JS题解代码

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let w = [];
let h = 0;

rl.on('line', (line) => {
    if (w.length === 0) {
        w = line.split(' ').map(Number);  // 读入n个数字
    } else if (h === 0) {
        h = parseInt(line);
        let n = w.length;
        if (n > h) {  // 每小时最多只能吃一颗桃树，因此没办法吃完所有桃树
            console.log(0);
        } else {
            let l = 1, r = 1e9;  // 二分左右边界
            while (l < r) {
                let mid = Math.floor((l + r) / 2);
                if (check(w, h, mid)) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            console.log(l);
        }
    }
});

function check(w, h, x) {
    let cnt = 0;  // 记录吃完所有桃树的时间
    for (let num of w) {
        cnt += Math.floor((num + x - 1) / x);  // 吃掉数量为num的一颗桃树所需要的时间
        if (cnt > h) {
            return false;
        }
    }
    return true;
}

四.代码讲解(Java&Python&C++&JS分别讲解)

Python题解代码解析：

1. 总体思路： 该Python代码通过二分查找的方式寻找孙悟空吃蟠桃的最小速度K，使得在规定的时间内能够吃完所有桃子。

2. 函数min_speed(N, H)：

   • 接收两个参数，N表示每棵桃树上的桃子数量的列表，H表示守卫回来的时间。
   • 计算所有桃子的总数total_peaches。
   • 初始化左边界left为1，右边界right为总桃子数。
   • 使用二分查找，在每次迭代中计算吃完所有桃子所需的时间time_needed，然后判断是否小于等于规定的时间H。
   • 如果小于等于H，更新最小速度min_speed为当前速度mid，并将右边界往左移；否则，将左边界往右移。
   • 最终返回最小速度min_speed。

3. 输入处理：

   • 通过input()获取输入的一行字符串，使用split()将其分割为每颗桃子的数量列表N。
   • 使用int(input())获取守卫回来的时间H。

4. 输出结果：

   • 打印调用min_speed(N, H)的结果。

JAVA题解代码解析：

1. 总体思路： 该Java代码使用了面向对象的风格，通过Scanner类进行输入，实现了与Python相似的二分查找思路。

2. 主函数：

   • 使用Scanner类获取输入的桃树数量n和守卫回来的时间h。
   • 创建一个长度为n的整数数组peaches，保存每棵桃树上的桃子数量。
   • 调用minSpeed(peaches, h)函数计算结果并打印。

3. 函数minSpeed：

   • 接收两个参数，peaches表示每棵桃树上的桃子数量的数组，h表示守卫回来的时间。
   • 计算所有桃子的总数totalPeaches。
   • 初始化左边界left为1，右边界right为总桃子数。
   • 使用二分查找，在每次迭代中判断是否能在规定时间内完成，如果可以则将右边界向左移，否则将左边界向右移。
   • 返回最终的速度，如果无解返回0。

4. 函数canFinish：

   • 判断给定速度是否能在规定时间内吃完所有桃子。
   • 计算所需时间，遍历每棵桃树，判断是否能在规定时间内吃完。

C/C++题解代码解析：

1. 总体思路： 该C++代码使用了STL的vector，通过数组保存每棵桃树上的桃子数量，实现了与前两种语言相似的二分查找思路。

2. 主函数：

   • 创建一个vector类型的数组peaches，用于保存每棵桃树上的桃子数量。
   • 使用循环读入每棵桃树上的桃子数量。
   • 读入守卫回来的时间h。
   • 使用二分查找计算结果并打印。

3. 二分查找过程：

   • 初始化左边界left为1，右边界right为1e9（表示10的9次方）。
   • 使用while循环，每次计算中间值mid，然后根据canFinish函数判断在规定时间内是否能吃完所有桃子。
   • 根据判断结果，更新左右边界，最终得到结果。

JS题解代码解析：

1. 总体思路： 该JavaScript代码使用了Node.js的readline模块进行输入，实现了与前三种语言相似的二分查找思路。

2. 输入处理：

   • 使用readline模块逐行读取输入，将第一行的n个数字保存到数组w，将第二行的数字保存到变量h。

3. 二分查找过程：

   • 初始化左边界left为1，右边界right为1e9。
   • 使用while循环，每次计算中间值mid，然后根据check函数判断在规定时间内是否能吃完所有桃子。
   • 根据判断结果，更新左右边界，最终得到结果。

4. 函数check：

   • 判断给定速度是否能在规定时间内吃完所有桃子。
   • 计算所需时间，遍历每棵桃树，判断是否能在规定时间内吃完。

寄语