猴子吃桃/爱吃蟠桃的孙悟空

题目描述

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

孙悟空可以决定他吃蟠桃的速度K个/小时, 每个小时选一颗桃树, 并从树上吃掉 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

输出:

5

示例2

输入:

2 3 4 5
3

输出:

0

题解

Python

import math

def can_finish(peaches, leave_hours, eat_speed):
    ans = 0
    for peach in peaches:
        # 每棵树上花的时间, 不够一个小时, 就算一个小时, 因为猴子要慢吃
        ans += math.ceil(peach / eat_speed)
    # 吃的总时间不大于离开的时间
    return ans <= leave_hours

def main():
    peaches = list(map(int, input().split()))
    hours = int(input())
    n = len(peaches)
    if n == 0 or n >= 1000 or hours <= 0 or hours >= 10000:
        print(0)
        return

    # 二分查找法找出吃的速度的最小值
    left = 1
    right = 10 ** 9
    while left < right:
        middle = left + (right - left) // 2
        if can_finish(peaches, hours, middle):
            right = middle
        else:
            left = middle + 1

    # 如果最快的速度仍然吃不完, 那就无解
    if left == right:
        print(0)
    else:
        print(left)


if __name__ == "__main__":
    main()