孙悟空吃蟠桃 - 华为OD统一考试

2024-02-14 15:12

本文主要是介绍孙悟空吃蟠桃 - 华为OD统一考试,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

OD统一考试(C卷)

分值: 200分

题解: Java / Python / C++

alt

题目描述

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

孙悟空可以决定他吃蟠桃的速度 K (个/每小时),每个小时选一棵桃树,并从树上吃掉 K 个,如果K大于该树上所有桃子个数,则全部吃掉,并且这一小时剩余的时间里不再吃桃。

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

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

输入描述

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

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

其中数字通过空格分割, NH 为正整数,每棵树上都有蟠桃,且 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 = peachs.length;// 每个小时只能选一棵桃树,因此任何速度都吃不完所有桃子if (n > H) {return 0;}int l = 0, r = Arrays.stream(peachs).max().orElse(0);while (l + 1 < r) {int mid = (l + r) / 2;if (ok(peachs, mid, H)) {r = mid;} else {l = mid;}}return r;}
}

Python

from typing import Listdef ok(peachs: List[int], speed: int, H: int) -> bool:""":param peachs: 每棵桃树上蟠桃的数量:param speed: 守卫每小时吃的桃子数量:param H: 守卫离开的时间:return:  每个小时只能选一棵桃树,能否在 H 小时内吃完所有的桃子"""time = 0for cnt in peachs:time += (cnt + speed - 1) // speed  # 向上取整return time <= Hdef solve(peachs: List[int], H: int) -> int:n = len(peachs)# 每个小时只能选一棵桃树,因此任何速度都吃不完所有桃子if n > H:return 0l, r = 0, max(peachs)while l + 1 < r:mid = (l + r) // 2if ok(peachs, mid, H):r = midelse:l = midreturn rif __name__ == '__main__':# 每棵桃树上蟠桃的数量peachs = list(map(int, input().split()))# 守卫离开的时间H = int(input())print(solve(peachs, H))

C++

#include <iostream>
#include <vector>
#include <algorithm>using namespace std;/*** 每个小时只能选一棵桃树,能否在 H 小时内吃完所有的桃子** @param peachs 每棵桃树上蟠桃的数量* @param speed  守卫每小时吃的桃子数量* @param H      守卫离开的时间* @return 每个小时只能选一棵桃树,能否在 H 小时内吃完所有的桃子*/
bool ok(const vector<int>& peachs, int speed, int H) {int time = 0;for (int cnt : peachs) {time += (cnt + speed - 1) / speed;  // 向上取整if(time > H) return false;}return true;
}/*** 计算守卫在 H 小时内能吃完所有的桃子的最小速度** @param peachs 每棵桃树上蟠桃的数量* @param H      守卫离开的时间* @return 守卫在 H 小时内能吃完所有的桃子的最小速度*/
int solve(const vector<int>& peachs, const int H) {int n = peachs.size();// 每个小时只能选一棵桃树,因此任何速度都吃不完所有桃子if (n > H) {return 0;}int l = 0, r = *max_element(peachs.begin(), peachs.end());while (l + 1 < r) {int mid = (l + r) / 2;if (ok(peachs, mid, H)) {r = mid;} else {l = mid;}}return r;
}int main() {// 每棵桃树上蟠桃的数量vector<int> peachs;int peach;while (cin >> peach) {peachs.push_back(peach);}// 守卫离开的时间int H = peachs.back();peachs.pop_back();cout << solve(peachs, H) << endl;return 0;
}

相关练习题

题号题目难易
LeetCode 16311631. 最小体力消耗路径中等
LeetCode 22262226. 每个小孩最多能分到多少糖果中等

‍❤️‍华为OD机试面试交流群每日真题分享): 加V时备注“华为od加群”

🙏整理题解不易, 如果有帮助到您,请给点个赞 ‍❤️‍ 和收藏 ⭐,让更多的人看到。🙏🙏🙏

这篇关于孙悟空吃蟠桃 - 华为OD统一考试的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/708845

相关文章

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源:安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供,流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材,流动式起重机司机大纲整理而成(含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析),掌握本资料和学校方法,考试容易。流动式起重机司机考试技

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和

软考系统规划与管理师考试证书含金量高吗?

2024年软考系统规划与管理师考试报名时间节点: 报名时间:2024年上半年软考将于3月中旬陆续开始报名 考试时间:上半年5月25日到28日,下半年11月9日到12日 分数线:所有科目成绩均须达到45分以上(包括45分)方可通过考试 成绩查询:可在“中国计算机技术职业资格网”上查询软考成绩 出成绩时间:预计在11月左右 证书领取时间:一般在考试成绩公布后3~4个月,各地领取时间有所不同

系统架构师考试学习笔记第三篇——架构设计高级知识(20)通信系统架构设计理论与实践

本章知识考点:         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识

828华为云征文|华为云Flexus X实例docker部署rancher并构建k8s集群

828华为云征文|华为云Flexus X实例docker部署rancher并构建k8s集群 华为云最近正在举办828 B2B企业节,Flexus X实例的促销力度非常大,特别适合那些对算力性能有高要求的小伙伴。如果你有自建MySQL、Redis、Nginx等服务的需求,一定不要错过这个机会。赶紧去看看吧! 什么是华为云Flexus X实例 华为云Flexus X实例云服务是新一代开箱即用、体

华为OD机试真题-学生方阵-2024年OD统一考试(E卷)

题目描述 学校组织活动,将学生排成一个矩形方阵。 请在矩形方阵中找到最大的位置相连的男生数量。这个相连位置在一个直线上,方向可以是水平的,垂直的,成对角线的或者呈反对角线的。 注:学生个数不会超过10000 输入描述 输入的第一行为矩阵的行数和列数, 接下来的 n行为矩阵元素,元素间用""分隔。 输出描述 输出一个整数,表示矩阵中最长的位

UML- 统一建模语言(Unified Modeling Language)创建项目的序列图及类图

陈科肇 ============= 1.主要模型 在UML系统开发中有三个主要的模型: 功能模型:从用户的角度展示系统的功能,包括用例图。 对象模型:采用对象、属性、操作、关联等概念展示系统的结构和基础,包括类图、对象图、包图。 动态模型:展现系统的内部行为。 包括序列图、活动图、状态图。 因为要创建个人空间项目并不是一个很大的项目,我这里只须关注两种图的创建就可以了,而在开始创建UML图

华为 HCIP-Datacom H12-821 题库 (13)

有需要题库的可以看主页置顶 1.可以携带外部路由的 tag 标签信息的是以下哪一类 LSA? A、4 类 LSA B、5 类 LSA  C、3 类 LSA  D、2 类 LSA 答案:B 解析: 暂无解析 2..两台路由器直连,并设定网络类型为 p2p 建立OSPF 邻居。那么两台路由器传输 OSPF 报文的目的 IP 地址是以下哪一项? A、使用组播地址 224.0.0.6 B

4G模块、WIFI模块、NBIOT模块通过AT指令连接华为云物联网服务器(MQTT协议)

MQTT协议概述 MQTT(Message Queuing Telemetry Transport)是一种轻量级的消息传输协议,它被设计用来提供一对多的消息分发和应用之间的通讯,尤其适用于远程位置的设备和高延迟或低带宽的网络。MQTT协议基于客户端-服务器架构,客户端可以订阅任意数量的主题,并可以发布消息到这些主题。服务器(通常称为MQTT Broker)则负责接受来自客户端的连接请求,并转发消

华为23年笔试题

消息传输 题目描述 在给定的 m x n (1 <= m, n <= 1000) 网格地图 grid 中,分布着一些信号塔,用于区域间通信。 每个单元格可以有以下三种状态:  值 0 代表空地,无法传递信号;  值 1 代表信号塔 A,在收到消息后,信号塔 A 可以在 1ms 后将信号发送给上下左右四个方向的信号塔; 值 2 代表信号塔 B,在收到消息后,信号塔 B 可以在 2ms