07-14 10:20 已编辑北京理工大学算法工程师发布于浙江

关注

最新华为OD机试真题-K小姐吃水果(100分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

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

👏 感谢大家的订阅➕ 和喜欢💗

📎在线评测链接

K小姐吃水果(100分)

alt

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

alt

🍰 K小姐吃水果

问题描述

K小姐非常喜欢吃水果，她发现了一个水果园，里面种植了 $N$ 棵果树，每棵树上都结了不同数量的果实。但是园丁LYA告诉K小姐，自己将在 $H$ 小时后回来，在此之前K小姐可以尽情享用水果。

K小姐决定每小时吃一棵树上的水果，她以 $K$ 个/小时的速度吃水果。如果一棵树上的水果数量小于 $K$ ，那么K小姐会在这一小时内吃完这棵树上的所有水果，并且在这一小时内不再吃其他树上的水果。

K小姐希望慢慢享受美味的水果，但又希望在LYA回来之前吃完所有的水果。你能帮助K小姐计算出她吃水果的最小速度 $K$ 吗？如果怎样都无法在规定时间内吃完所有水果，则输出0。

注意， $K$ 为整数。

输入格式

第一行包含 $N$ 个正整数，表示每棵果树上的水果数量。

第二行包含一个正整数 $H$ ，表示LYA离开的时间。

其中 $1 \leq N \leq 10000$ ， $1 \leq H \leq 10000$ ，每棵果树上至少有1个水果。

输出格式

输出一个整数，表示K小姐吃水果的最小速度 $K$ 。

如果无法在规定时间内吃完所有水果，则输出0。

样例输入1

2 3 4 5
4

样例输出1

样例输入2

2 3 4 5 
3

样例输出2

样例输入3

30 11 23 4 20
6

样例输出3

数据范围

对于 $30\%$ 的数据， $1 \leq N \leq 30$ 。对于 $60\%$ 的数据， $1 \leq N \leq 1000$ 。对于 $100\%$ 的数据， $1 \leq N \leq 10000$ 。

题解

本题可以使用二分答案的思想来解决。我们可以将吃水果的速度 $K$ 作为二分的对象，判断是否存在一个速度 $K$ ，使得K小姐可以在 $H$ 小时内吃完所有的水果。

首先，我们可以确定速度 $K$ 的上下界。最小速度显然为1，最大速度可以取所有果树中水果数量的最大值。因为如果速度大于最大的水果数量，那么每小时都可以吃完一棵树，这就是最快的速度了。

然后，我们就可以在[1, 最大值]范围内二分速度 $K$ 。对于每个速度 $K$ ，我们模拟K小姐以这个速度吃水果的过程，计算吃完所有水果需要的时间。如果时间不超过 $H$ ，说明这个速度可行，我们可以尝试更小的速度；否则，这个速度太慢了，我们需要提高速度。

通过二分查找，我们最终可以找到最小的速度 $K$ ，使得K小姐恰好可以在 $H$ 小时内吃完所有水果。如果二分结束后，最小速度仍然大于最大值，说明怎样都无法在规定时间内吃完水果，此时返回0。

时间复杂度 $O(N \log M)$ ，其中 $M$ 为果树上水果数量的最大值。二分查找的次数为 $O(\log M)$ ，每次需要遍历所有果树模拟吃水果的过程，耗时 $O(N)$ 。

参考代码

Python

import math

# 读取输入
cnts = list(map(int, input().split()))
h = int(input())

def check(speed):
    cost = 0
    for cnt in cnts:
        cost += math.ceil(cnt / speed)
        if cost > h:
            return False
    return True

def solve():
    n = len(cnts)
    if n > h:
        return 0
    
    maxSpeed = max(cnts)
    if n == h:
        return maxSpeed
    
    minSpeed = 1
    ans = maxSpeed
    
    while m

剩余60%内容，订阅专栏后可继续查看/也可单篇购买

最新华为OD机试-D卷文章被收录于专栏

本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测订阅专栏后请私信留下你想要的用户名，学长这边帮你开通对应的 OJ 账号和权限。