最新华为OD机试真题-K小姐吃水果(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
最新华为OD机试D卷目录,全、新、准,题目覆盖率达 95% 以上,支持题目在线评测
最新华为OD机试目录: https://www.nowcoder.com/discuss/636153620743897088?sourceSSR=users
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
🍰 K小姐吃水果
问题描述
K小姐非常喜欢吃水果,她发现了一个水果园,里面种植了 棵果树,每棵树上都结了不同数量的果实。但是园丁LYA告诉K小姐,自己将在
小时后回来,在此之前K小姐可以尽情享用水果。
K小姐决定每小时吃一棵树上的水果,她以 个/小时的速度吃水果。如果一棵树上的水果数量小于
,那么K小姐会在这一小时内吃完这棵树上的所有水果,并且在这一小时内不再吃其他树上的水果。
K小姐希望慢慢享受美味的水果,但又希望在LYA回来之前吃完所有的水果。你能帮助K小姐计算出她吃水果的最小速度 吗?如果怎样都无法在规定时间内吃完所有水果,则输出0。
注意, 为整数。
输入格式
第一行包含 个正整数,表示每棵果树上的水果数量。
第二行包含一个正整数 ,表示LYA离开的时间。
其中 ,
,每棵果树上至少有1个水果。
输出格式
输出一个整数,表示K小姐吃水果的最小速度 。
如果无法在规定时间内吃完所有水果,则输出0。
样例输入1
2 3 4 5
4
样例输出1
5
样例输入2
2 3 4 5
3
样例输出2
0
样例输入3
30 11 23 4 20
6
样例输出3
23
数据范围
对于 的数据,
。 对于
的数据,
。 对于
的数据,
。
题解
本题可以使用二分答案的思想来解决。我们可以将吃水果的速度 作为二分的对象,判断是否存在一个速度
,使得K小姐可以在
小时内吃完所有的水果。
首先,我们可以确定速度 的上下界。最小速度显然为1,最大速度可以取所有果树中水果数量的最大值。因为如果速度大于最大的水果数量,那么每小时都可以吃完一棵树,这就是最快的速度了。
然后,我们就可以在[1, 最大值]范围内二分速度 。对于每个速度
,我们模拟K小姐以这个速度吃水果的过程,计算吃完所有水果需要的时间。如果时间不超过
,说明这个速度可行,我们可以尝试更小的速度;否则,这个速度太慢了,我们需要提高速度。
通过二分查找,我们最终可以找到最小的速度 ,使得K小姐恰好可以在
小时内吃完所有水果。如果二分结束后,最小速度仍然大于最大值,说明怎样都无法在规定时间内吃完水果,此时返回0。
时间复杂度 ,其中
为果树上水果数量的最大值。二分查找的次数为
,每次需要遍历所有果树模拟吃水果的过程,耗时
。
参考代码
- 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%内容,订阅专栏后可继续查看/也可单篇购买
本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测 订阅专栏后请私信留下你想要的 用户名,学长这边帮你开通对应的 OJ 账号和权限。