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,最大速度是树上最多蟠桃的数量。
-
在这个范围内进行二分查找。对于每个中间值(速度),检查是否能在规定时间内吃完所有蟠桃。
-
如果当前速度可以吃完所有蟠桃,就尝试更小的速度;如果不能吃完,就尝试更大的速度。
-
最终,找到满足条件的最小速度。
这个方法之所以有效,是因为吃桃的速度与吃完所有桃子所需的时间成反比。速度越快,需要的时间越少,这是一个单调关系。因此,可以使用二分查找来快速找到临界点。
关键点在于如何判断给定速度下是否能吃完所有桃子。对于每棵树,可以用 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;
}
#OD#本专栏收集并整理了一些刷题笔记