【2023华为od-C卷-第三题-孙悟空吃蟠桃】100%通过率（JS&Java&Python&C++）_孙悟空爱吃蟠桃,有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 n 棵桃树,每颗树

本题已有网友报告代码100%通过率
本题视频讲解：视频讲解

OJ &答疑服务

购买任意专栏，即可添加博主vx:utheyi，获取答疑/辅导服务

OJ权限获取可以在购买专栏后访问网站：首页 - CodeFun2000

题目描述

孙悟空爱吃蟠桃，有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 $N$棵蟠桃树，每颗树上都桃子，守卫将在 $H$ 小时后回来。

孙悟空可以决定他吃蟠桃的速度 $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
1
2

输出

5
1

样例2

输入

2 3 4 5
3
1
2

输出

0
1

样例3

输入

30 11 23 4 20
6
1
2

输出

23
1

思路：二分答案

和LeetCode这道题基本上一模一样，没有写过二分答案的同学可以先去写一下这道题：875. 爱吃香蕉的珂珂 - 力扣（LeetCode）\

首先，考虑一种没办法吃完所有桃树的情况，因为一次最多只能吃一棵桃树，如果桃树的总数量$n$比$h$还要大，那一定是不能满足条件的，直接输出0即可

由于，吃的速度$k$越大，越容易满足条件，极端情况下，$k$取正无穷，是一定可以满足条件的，反之$k$越小，则越不容易满足条件，因此是符合单调性的，可以使用二分查找求解。

二分速度$k$，假设当前的速度为$mid$,则可以遍历数组，维护一个变量$cnt$表示吃完所有香蕉所需要的时间，对于$x$根香蕉来说，所需要的时间为$\frac{x}{mid}$上取整，因此累加$\frac{x+mid-1}{mid}$即可，最终判断是否有$cnt\le h$。

JavaScript代码

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

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

Java代码

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] input = sc.nextLine().split(" ");  // 读入n个数字
        int h = Integer.parseInt(sc.nextLine());
        int n = input.length;
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = Integer.parseInt(input[i]);
        }
        if (n > h) {  // 每小时最多只能吃一颗桃树，因此没办法吃完所有桃树
            System.out.println(0);
        } else {
            int l = 1, r = (int) 1e9;  // 二分左右边界
            while (l < r) {
                int mid = l + (r - l) / 2;
                if (check(w, h, mid)) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            System.out.println(l);
        }
    }

    static boolean check(int[] w, int h, int x) {
        int cnt = 0;  // 记录吃完所有桃树的时间
        for (int num : w) {
            cnt += (num + x - 1) / x;  // 吃掉数量为num的一颗桃树所需要的时间
            if (cnt > h) {
                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

C++代码

#include<bits/stdc++.h>  // 引入所有标准库头文件
using namespace std;
const int N=1E5+10;  // 定义数组大小
int w[N],h,n;  // 定义桃树数量、小时数和桃树数组

bool check(int x){  // 判断当吃的速度为x的时候，是否能吃完所有桃树
    int cnt=0;  // 记录吃完所有桃树的时间
    for(int i=1;i<=n;i++){
        cnt+=(w[i]+x-1)/x;  // 吃掉数量为w[i]的一颗桃树所需要的时间
        if(cnt>h)return false;  // 如果吃完所有桃树的时间超过了规定时间，返回false
    }
    return true;  // 如果吃完所有桃树的时间不超过规定时间，返回true
}

int main(){
    while(cin>>w[++n]);  // 读入桃树数量和每颗桃树的数量
    h=w[--n];  // 最后一个数为规定时间，将其赋值给h
    --n;  // 桃树数量减一
    if(n>h)puts("0");  // 如果桃树数量大于规定时间，输出0
    else{
        int l=1,r=1e9;  // 二分左右边界
        while(l<r){
            int mid=l+r>>1;  // 取中间值
            if(check(mid))r=mid;  // 如果能吃完所有桃树，将右边界移动到中间值
            else l=mid+1;  // 如果不能吃完所有桃树，将左边界移动到中间值+1
        }
        cout<<l<<endl;  // 输出最小速度
    }
    return 0;
}

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

Python代码

w=list(map(int,input().split()))  #读入n个数字
h=int(input())  
n=len(w)
if n>h:  #每小时最多只能吃一颗桃树，因此没办法吃完所有桃树
    print(0)
else:
    def check(x):  #判断当吃的速度为x的时候，是否能吃完所有桃树
        cnt=0  #记录吃完所有桃树的时间
        for num in w:
            cnt+=(num+x-1)//x  #吃掉数量为num的一颗桃树所需要的时间
            if cnt>h:
                return False
        return True
        
    l,r=1,10**9  #二分左右边界
    while l<r:
        mid=l+r>>1
        if check(mid):
            r=mid
        else:
            l=mid+1
    print(l)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23