【最新华为OD机试E卷】爱吃蟠桃的孙悟空(100分)

🍭 大家好这里是春秋招笔试突围 ，一枚热爱算法的程序员

💻 ACM金牌🏅️团队 ｜ 大厂实习经历 ｜ 多年算法竞赛经历

✨ 本系列打算持续跟新华为OD-E/D卷的多语言AC题解

🧩 大部分包含 Python / C / Javascript / Java / Cpp 多语言代码

👏 感谢大家的订阅➕ 和 喜欢💗 和手里的小花花🌸

最新华为OD机试E卷全、新、准，题目覆盖率达 95% 以上，其中D卷题目全部支持在线评测，E卷题目正在持续上线中~

最新华为OD机试专栏: https://www.nowcoder.com/creation/manager/columnDetail/MgbyJj

🎀关于华为OD

• ✨华为OD的概念 华为的大部分社会招聘采用了被称为OD（Outsourcing Dispatch）模式，这是一种与德科共同进行的招聘方式。在这种模式下，被招聘的员工通常被定级在13至17级，这些员工被视为华为的储备人才。华为每年会从这些OD项目中选拔表现出色的员工，并将他们转为正式员工。
• ⌚️华为 OD 应聘流程

  • 第一步：投递简历

    • 提供姓名、邮箱、手机号、身份证号，用于锁定，所以投递前需要考虑清楚，投到项目组之后，一般不会转给另一个项目的 HR 了，也就是被锁定。

  • 第二步：机试

    • 3 道算法题，400 分满分，一般 1 个月的准备时间，华为机试必须要 150 分以上，没有过半年之后才能参加下一次考试。

  • 第三步：技术面

    • 2 轮技术面试。

  • 第四步：HR 与主管面试

  • 第五步：录用，发 offer

🍓OJ题目截图

🍑 爱吃蟠桃的孙悟空

问题描述

孙悟空来到了蟠桃园偷吃蟠桃。蟠桃园里有 棵桃树，每棵树上都有一定数量的蟠桃。守卫离开了 小时，孙悟空想在守卫回来之前吃掉所有的蟠桃。

孙悟空每小时可以选择一棵树，以速度 （个/小时）吃桃。如果树上的桃子数量少于 ，孙悟空会把这棵树上的桃子全部吃完，然后在这一小时内不再吃其他树上的桃子。

孙悟空想要尽可能慢慢品尝蟠桃，但又要确保在守卫回来之前吃完所有的桃子。请计算孙悟空在 小时内吃掉所有蟠桃的最小速度 （ 为正整数）。如果无论以什么速度都无法在规定时间内吃完所有蟠桃，则返回 。

输入格式

第一行输入 个正整数，表示 棵桃树上的蟠桃数量，数字间用空格分隔。

第二行输入一个正整数 ，表示守卫离开的时间（小时）。

输出格式

输出一个整数，表示孙悟空吃掉所有蟠桃的最小速度 。如果无解或输入异常，输出 。

样例输入

输入样例1：

2 3 4 5 4
5

输入样例2：

2 3 4 5 3

输入样例3：

30 11 23 4 20
6

样例输出

输出样例1：

5

输出样例2：

0

输出样例3：

23

样例解释

对于样例1，孙悟空以每小时吃5个蟠桃的速度，可以在5小时内吃完所有蟠桃。这是最小的可行速度。

对于样例2，即使孙悟空以最快速度吃桃，也无法在3小时内吃完所有蟠桃，因此输出0。

对于样例3，孙悟空需要以每小时至少吃23个蟠桃的速度，才能在6小时内吃完所有蟠桃。

数据范围

• 
• 
• 每棵树上的蟠桃数量为正整数

题解

这道题目可以使用二分查找算法来解决。

解题思路如下：

1. 首先，确定二分查找的范围。最小速度是1，最大速度是树上最多蟠桃的数量。

2. 在这个范围内进行二分查找。对于每个中间值（速度），检查是否能在规定时间内吃完所有蟠桃。

3. 如果当前速度可以吃完所有蟠桃，就尝试更小的速度；如果不能吃完，就尝试更大的速度。

4. 最终，找到满足条件的最小速度。

这个方法之所以有效，是因为吃桃的速度与吃完所有桃子所需的时间成反比。速度越快，需要的时间越少，这是一个单调关系。因此，可以使用二分查找来快速找到临界点。

关键点在于如何判断给定速度下是否能吃完所有桃子。对于每棵树，可以用 ceil(桃子数 / 速度) 来计算需要的小时数。如果所有树的总小时数不超过 ，则该速度可行。

参考代码

• Python

import math

def can_eat_all(peaches, speed, hours):
    """
    检查是否能以给定速度在规定时间内吃完所有桃子
    """
    time_needed = sum(math.ceil(p / speed) for p in peaches)
    return time_needed <= hours

def min_eating_speed(peaches, hours):
    """
    计算吃完所有桃子的最小速度
    """
    if len(peaches) > hours:
        return 0
    
    left, right = 1, max(peaches)
    while left < right:
        mid = (left + right) // 2
        if can_eat_all(peaches, mid, hours):
            right = mid
        else:
            left = mid + 1
    
    return left

# 读取输入
peaches = list(map(int, input().split()))
hours = int(input())

# 计算并输出结果
print(min_eating_speed(peaches, hours))

• C

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAX_N 10000

int can_eat_all(int* peaches, int n, int speed, int hours) {
    int time_needed = 0;
    for (int i = 0; i < n; i++) {
        time_needed += (peaches[i] + speed - 1) / speed;
        if (time_needed > hours) return 0;
    }
    return 1;
}

int min_eating_speed(int* peaches, int n, int hours) {
    if (n > hours) return 0;
    
    int left = 1, right = peaches[0];
    for (int i = 1; i < n; i++) {
        if (peaches[i] > right) right = peaches[i];
    }
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (ca