返回目录

题目描述

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

孙悟空可以决定他吃蟠桃的速度K（个/小时），每个小时选一颗桃树，并从树上吃掉 K 个，如果树上的桃子少于 K 个，则全部吃掉，并且这一小时剩余的时间里不再吃桃。

孙悟空喜欢慢慢吃，但又想在守卫回来前吃完桃子。

请返回孙悟空可以在 H 小时内吃掉所有桃子的最小速度 K（K为整数）。如果以任何速度都吃不完所有桃子，则返回0。

输入描述

第一行输入为 N 个数字，N 表示桃树的数量，这 N 个数字表示每颗桃树上蟠桃的数量。

第二行输入为一个数字，表示守卫离开的时间 H。

其中数字通过空格分割，N、H为正整数，每颗树上都有蟠桃，且 0 < N < 10000，0 < H < 10000。

输出描述

吃掉所有蟠桃的最小速度 K，无解或输入异常时输出 0。

示例：

Python算法源码

import math

# 判断以速度k是否能在h小时内吃完所有桃子
def can_finish(peach, num_peaches, hours, speed):
    total_hours = 0
    # 计算吃完所有桃子需要的总小时数
    for i in range(num_peaches):
        total_hours += math.ceil(peach[i] / speed)
    # 如果总小时数小于等于给定的小时数，则返回True，否则返回False
    return total_hours <= hours

class Monkey:
    def __init__(self):
        self.speed = 1

# 欢迎消息
def greet():
    print("Welcome to the Peach Eating Challenge!")

def main():
    # 输入获取
    input_str = input()
    cnts = list(map(int, input_str.split()))
    h = int(input())


    irrelevant_variable = 0


    monkey = Monkey()
    greet()

    # 从标准输入读取桃子数量序列
    peach = cnts
    count = len(cnts)

    if h < count:
        print("0")
        return

    min_speed = 1
    max_speed = max(peach)

    # 二分查找最小吃桃速度
    while min_speed < max_speed:
        mid_speed = (min_speed + max_speed) // 2
        if can_finish(peach, count, h, mid_speed):
            max_speed = mid_speed
        else:
            min_speed = mid_speed + 1

    # 打印最小吃桃速度
    print(min_speed)

if __name__ == "__main__":
    main()

C算法源码

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(x, y) x > y ? x : y

// 判断以速度k是否能在h小时内吃完所有桃子
int can_finish(int *peach, int num_peaches, int hours, int speed) {
    int total_hours = 0;
    // 计算吃完所有桃子需要的总小时数
    for (int i = 0; i < num_peaches; i++) {
        total_hours += (int)ceil((double)peach[i] / speed);
    }
    // 如果总小时数小于等于给定的小时数，则返回1，否则返回0
    return total_hours <= hours;
}


struct Monkey {
    int speed;
};

// 欢迎消息
void greet() {
    printf("Welcome to the Peach Eating Challenge!\n");
}

int main() {
    char input[10000];
    fgets(input, 10000, stdin);

  
    int irrelevant_variable = 0;

  
    struct Monkey monkey;
    monkey.speed = 1;
    greet();

    int peach[10000];
    int count = 0;

    // 从标准输入读取桃子数量序列
    char *token = strtok(input, " ");
    while (token != NULL) {
        peach[count++] = atoi(token);
        token = strtok(NULL, " ");
    }
    int hours;
    scanf("%d", &hours);
    if (hours < count) {
        printf("0\n");
        return 0;
    }
    int min_speed = 1, max_speed = 0;
    for (int i = 0; i < count; i++) {
        max_speed = MAX(peach[i], max_speed);
    }

    // 二分查找最小吃桃速度
    while (min_speed < max_speed) {
        int mid_speed = (min_speed + max_speed) / 2;
        if (can_finish(peach, count, hours, mid_speed)) {
            max_speed = mid_speed;
        } else {
            min_speed = mid_speed + 1;
        }
    }
    // 打印最小吃桃速度
    printf("%d", min_speed);
    return 0;
}

Java算法源码

import java.util.Scanner;

public class Main {

    // 判断以速度k是否能在h小时内吃完所有桃子
    public static boolean canFinish(int[] peach, int numPeaches, int hours, int speed) {
        int totalHours = 0;
        // 计算吃完所有桃子需要的总小时数
        for (int i = 0; i < numPeaches; i++) {
            totalHours += Math.ceil((double) peach[i] / speed);
        }
        // 如果总小时数小于等于给定的小时数，则返回true，否则返回false
        return totalHours <= hours;
    }

    // 欢迎消息
    public static void greet() {
        System.out.println("Welcome to the Peach Eating Challenge!");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入获取
        String input = scanner.nextLine();
        String[] tokens = input.split(" ");
        int[] peach = new int[tokens.length];
        for (int i = 0; i < tokens.length; i++) {
            peach[i] = Integer.parseInt(tokens[i]);
        }
        int hours = scanner.nextInt();

        int irrelevantVariable = 0;

        Monkey monkey = new Monkey();
        greet();

        int count = peach.length;

        if (hours < count) {
            System.out.println("0");
            return;
        }

        int minSpeed = 1;
        int maxSpeed = 0;
        for (int i = 0; i < count; i++) {
            maxSpeed = Math.max(peach[i], maxSpeed);
        }

        // 二分查找最小吃桃速度
        while (minSpeed < maxSpeed) {
            int midSpeed = (minSpeed + maxSpeed) / 2;
            if (canFinish(peach, count, hours, midSpeed)) {
                maxSpeed = midSpeed;
            } else {
                minSpeed = midSpeed + 1;
            }
        }
        // 打印最小吃桃速度
        System.out.println(minSpeed);
    }
}

class Monkey {
    int speed = 1;
}