孙悟空吃蟠桃 - 华为OD统一考试(C卷)
OD统一考试(C卷)
分值: 200分
题解: Java / Python / C++
题目描述
孙悟空爱吃蟠桃,有一天趁着蟠桃园守卫不在来偷吃。已知蟠桃园有 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
示例3
输入:
30 11 23 4 20
6
输出:
23
题解
结合以上的题目和以下题目代码解法总结一些题解信息。
从以下几点方面: 题目属于什么类型的算法题(例如,动态规划、DFS、BFS、贪心、双指针 ...),解题思路,代码大致描述,时间复杂度,空间复杂度,及同类型 leetcode.cn 的题目
Java
import java.util.Arrays;
import java.util.Scanner;
/**
* @author code5bug
*/
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 每棵桃树上蟠桃的数量
int[] peachs = Arrays.stream(scanner.nextLine().split(" "))
.mapToInt(Integer::parseInt).toArray();
// 守卫离开的时间
int H = scanner.nextInt();
System.out.println(solve(peachs, H));
}
/**
* 每个小时只能选一棵桃树,能否在 H 小时内吃完所有的桃子
*
* @param peachs 每棵桃树上蟠桃的数量
* @param speed 守卫每小时吃的桃子数量
* @param H 守卫离开的时间
* @return 每个小时只能选一棵桃树,能否在 H 小时内吃完所有的桃子
*/
private static boolean ok(int[] peachs, int speed, int H) {
int time = 0;
for (int cnt : peachs) {
time += (cnt + speed - 1) / speed; // 向上取整
}
return time <= H;
}
/**
* 计算守卫在 H 小时内能吃完所有的桃子的最小速度
*
* @param peachs 每棵桃树上蟠桃的数量
* @param H 守卫离开的时间
* @return 守卫在 H 小时内能吃完所有的桃子的最小速度
*/
private static int solve(int[] peachs, int H) {
int n
剩余60%内容,订阅专栏后可继续查看/也可单篇购买
华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。