OD 算法题 B卷【猴子吃桃】

猴子吃桃

• 猴子喜欢吃桃，桃园有N棵桃树，第i棵桃树上有Ni个桃，看守将在H(>=N)小时后回来；
• 猴子可以决定吃桃的速度K(个/小时)，每个小时他会选择一棵桃树，从中吃掉K个桃，如果这棵树上的桃数小于K，他将吃掉这棵树上所有的桃，然后这一小时内不再吃其余桃树上的桃；
• 猴子喜欢慢慢吃，但仍想在看守回来之前吃完所有的桃；
• 求猴子可以在H小时内吃掉所有桃子的最小速度K（K为整数）

输入描述:
输入一行数字，前面的数字表示每颗树桃子的个数，最后一个数表示H小时；
输出描述:
吃掉所有桃子的最小速度K(整数) 或者输入异常时输出-1

示例1
输入：
3 11 6 7 8
输出：
4

示例2
输入：
10 20 14 23 21 45 31 7
输出：
45

python实现:

• 二分法，选择一个合适的K整数速度；

import matherror = Falsearr = list(map(int, input().strip().split()))
h = arr.pop()
n = len(arr)# 输入异常
if h < n or any([i <= 0 for i in arr]):error = Truedef eat_up(k):""" 根据当前的速度k, 在h小时内能否吃完 """global arr, hused_h = 0for i in arr:used_h += math.ceil(i / k)return used_h <= h# 最小速度
left = 1
right = sum(arr)  # 最大速度 (一小时吃完)
while left <= right:mid = (left + right) // 2if eat_up(mid):# 能在H小时内吃完，则降低速度right = mid - 1else:left = mid + 1if error:print(-1)
else:print(left)