刷题笔记合集🔗

爱吃蟠桃的孙悟空

问题描述

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

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

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

输入格式

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

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

输出格式

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

样例输入

输入样例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 (can_eat_all(peaches, n, mid, hours)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    int peaches[MAX_N];
    int n = 0, hours;
    
    // 读取输入
    while (scanf("%d", &peaches[n]) == 1) {
        n++;
        if (getchar() == '\n') break;
    }
    scanf("%d", &hours);
    
    // 计算并输出结