E卷-(100分)爱吃蟠桃的孙悟空

爱吃蟠桃的孙悟空

问题描述

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

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

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

输入格式

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

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

输出格式

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

样例输入

输入样例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);
    
    // 计算并输出结果
    printf("%d\n", min_eating_speed(peaches, n, hours));
    
    return 0;
}

• Javascript

// 读取输入
var readline = require('readline');
var rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

var lines = [];

rl.on('line', function(line) {
    lines.push(line);
    if (lines.length === 2) {
        var peaches = lines[0].split(' ').map(Number);
        var hours = parseInt(lines[1]);
        console.log(minEatingSpeed(peaches, hours));
        rl.close();
    }
});

/**
 * 检查是否能以给定速度在规定时间内吃完所有桃子
 * @param {number[]} peaches - 每棵树上的桃子数量
 * @param {number} speed - 吃桃子的速度
 * @param {number} hours - 可用的小时数
 * @return {boolean} 是否能吃完所有桃子
 */
function canEatAll(peaches, speed, hours) {
    var timeNeeded = 0;
    for (var i = 0; i < peaches.length; i++) {
        timeNeeded += Math.ceil(peaches[i] / speed);
        if (timeNeeded > hours) return false;
    }
    return true;
}

/**
 * 计算吃完所有桃子的最小速度
 * @param {number[]} peaches - 每棵树上的桃子数量
 * @param {number} hours - 可用的小时数
 * @return {number} 最小速度，如果无法在规定时间内吃完则返回0
 */
function minEatingSpeed(peaches, hours) {
    if (peaches.length > hours) return 0;
    
    var left = 1;
    var right = Math.max.apply(null, peaches);
    
    while (left < right) {
        var mid = Math.floor((left + right) / 2);
        if (canEatAll(peaches, mid, hours)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

• Java

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取输入
        String[] input = scanner.nextLine().split(" ");
        int[] peaches = Arrays.stream(input).mapToInt(Integer::parseInt).toArray();
        int hours = scanner.nextInt();
        
        // 计算并输出结果
        System.out.println(minEatingSpeed(peaches, hours));
        
        scanner.close();
    }
    
    private static boolean canEatAll(int[] peaches, int speed, int hours) {
        int timeNeeded = 0;
        for (int p : peaches) {
            timeNeeded += (p + speed - 1) / speed;
            if (timeNeeded > hours) return false;
        }
        return true;
    }
    
    private static int minEatingSpeed(int[] peaches, int hours) {
        if (peaches.length > hours) return 0;
        
        int left = 1;
        int right = Arrays.stream(peaches).max().getAsInt();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (canEatAll(peaches, mid, hours)) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        
        return left;
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

bool canEatAll(const vector<int>& peaches, int speed, int hours) {
    int timeNeeded = 0;
    for (int p : peaches) {
        timeNeeded += ceil(static_cast<double>(p) / speed);
        if (timeNeeded > hours) return false;
    }
    return true;
}

int minEatingSpeed(const vector<int>& peaches, int hours) {
    if (peaches.size() > hours) return 0;
    
    int left = 1;
    int right = *max_element(peaches.begin(), peaches.end());
    
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (canEatAll(peaches, mid, hours)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

int main() {
    vector<int> peaches;
    int num;
    
    // 读取输入
    while (cin >> num) {
        peaches.push_back(num);
        if (cin.get() == '\n') break;
    }
    
    int hours;
    cin >> hours;
    
    // 计算并输出结果
    cout << minEatingSpeed(peaches, hours) << endl;
    
    return 0;
}