华为od机试真题 — 分披萨(Python)
题目描述
“吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨,并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。
但是粗心服务员将披萨切成了每块大小都完全不同奇数块,且肉眼能分辨出大小。
由于两人都想吃到最多的披萨,他们商量了一个他们认为公平的分法:从“吃货”开始,轮流取披萨。
除了第-块披萨可以任意选取以外,其他都必须从缺口开始选。 他俩选披萨的思路不同。
“馋嘴”每次都会选最大块的拨萨,而且“吃货”知道“馋嘴”的想法。
已知披萨小块的数量以及每块的大小,求“吃货”能分得的最大的披萨大小的总和。
输入描述
第1行为一个正整数奇数 N
,表示披萨小块数量。其中 3 ≤ N
< 500
接下来的第 2 行到第 N
+1 (共 N
行),每行为一个正整数,表示第i块披萨的大小, 1≤i
≤N
。
披萨小块从某一块开始,按照一个方向次序顺序编号为 1 ~ N
,每块披萨的大小范围为[1,2147483647]。
输出描述
”吃货“能分得到的最大的披萨大小的总和。
示例1
输入:
5
8
2
10
5
7输出:
19说明:
此例子中,有 5 块披萨。每块大小依次为 8 、2 、10 、5 、7。
按照如下顺序拿披萨,可以使”吃货拿到最多披萨:
“吃货”拿大小为 10 的披萨
“馋嘴”拿大小为5的披萨
“吃货”拿大小为7 的披萨
“馋嘴”拿大小为 8 的披萨
”吃货“拿大小为2 的披萨
至此,披萨瓜分完毕,”吃货“拿到的披萨总大小为 10+7+2=19
可能存在多种拿法,以上只是其中一种。
解题思路
解题思路
- 记忆化搜索:定义一个递归函数
f(l, r, t)
来表示从区间[l, r]
里,“吃货”能分得的最大披萨大小的总和。这里l
和r
分别表示区间的左边界和右边界,t
表示剩余的次数。- 贪心选择:每次“馋嘴”都会选择当前区间内最大的披萨块,这会影响到下一步“吃货”的选择。因此,我们需要在“吃货”选择之前模拟“馋嘴”的贪心选择,以确保“吃货”能得到最大总和。
- 递归处理:递归地缩小问题规模,通过模拟“吃货”在每一步的选择,并记录下最优结果。
代码描述
- 输入处理:读取输入的披萨块数量
n
和每块披萨的大小。- 缓存优化:使用
functools.cache
来缓存递归结果,避免重复计算。- 递归函数
f
:
- 参数:
l
为左边界,r
为右边界,t
为剩余次数。- 基本情况:如果剩余次数
t
小于等于1,则返回0。- 贪心选择:模拟“馋嘴”选择当前区间内的最大披萨块,更新
l
或r
。- 动态规划选择:计算“吃货”选择左边界
l
或右边界r
时的最大总和,并返回其中较大的值。- 主逻辑:通过遍历每块披萨,计算“吃货”从该块披萨开始能得到的最大总和。
Python
from functools import cachen = int(input())
pizza = list(int(input()) for _ in range(n))@cache
def f(l: int, r: int, t: int) -> int:""":param l: 左边界:param r: 右边界:param t: 剩余次数:return: 返回 “吃货” 最优选择时可以分到的披萨总和"""global n, pizzaif t <= 1:return 0l, r = (l + n) % n, r % n# “馋嘴”选择最大的一块if pizza[l] >= pizza[r]:l = (l - 1 + n) % nelse:r = (r + 1) % n# “吃货”选择 pizza[l]s1 = pizza[l] + f(l - 1, r, t - 2)# “吃货”选择 pizza[r]s2 = pizza[r] + f(l, r + 1, t - 2)return max(s1, s2)print(max(pizza[i] + f(i - 1, i + 1, n - 1) for i in range(n)))
@cache
的作用和使用
作用
- 性能优化:通过缓存函数的返回值,避免对相同输入的函数进行多次计算。
- 简洁代码:使用装饰器的方式可以使代码更加简洁和易读。
使用方法
- 在函数定义的上方添加
@cache
装饰器即可。
示例方法
from functools import cache@cache
def fibonacci(n):if n < 2:return nreturn fibonacci(n - 1) + fibonacci(n - 2)print(fibonacci(50))
在上述例子中,
fibonacci
函数使用了@cache
装饰器。当计算fibonacci(50)
时,fibonacci
函数会缓存所有中间结果,避免了大量重复计算,使得计算速度显著提升。
@cache
与 @lru_cache
的区别
-
@cache
:- 缓存所有的函数调用结果,直到程序结束或缓存被手动清除。
- 不限制缓存大小,可能会导致内存占用较大。
-
@lru_cache
:- Least Recently Used (LRU) 缓存,会限制缓存大小,默认最大缓存大小为 128,可以通过参数调整。
- 当缓存满了,会自动清除最久未使用的缓存项,以保持缓存大小在设定范围内。
-
示例代码
from functools import lru_cache@lru_cache(maxsize=128)def fibonacci(n):if n < 2:return nreturn fibonacci(n - 1) + fibonacci(n - 2)print(fibonacci(50))
相关练习题
题号 | 题目 | 难易 |
---|---|---|
LeetCode 486 | 486. 预测赢家 | 中等 |
LeetCode 464 | 464. 我能赢吗 | 中等 |
2024华为OD机试(C卷+D卷)最新题库【超值优惠】Java/Python/C++合集
🙏整理题解不易, 如果有帮助到您,请给点个赞 ❤️ 和收藏 ⭐,让更多的人看到。🙏🙏🙏
相关文章:

华为od机试真题 — 分披萨(Python)
题目描述 “吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨,并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。 但是粗心服务员将披萨切成了每块大小都完全不同奇数块,且肉眼能分辨出大小。 由于两人都想吃到最多的披萨,他们商量…...
ubuntu22.04 安装boost
下载boost压缩包,我这里上传了一份1_81_0版本tar -xzvf boost_1_81_0.tar.gzcd boost_1_81_0/sudo apt install build-essential g autotools-dev libicu-dev libbz2-dev -ysudo ./bootstrap.sh --prefix/usr/./b2sudo ./b2 install 上述7步完成后,相关…...

基于JAVA+SpringBoot+uniapp的心理小程序(小程序版本)
✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 技术范围:SpringBoot、Vue、SSM、HLMT、Jsp、SpringCloud、Layui、Echarts图表、Nodejs、爬…...

C语言 ——— 输入两个正整数,求出最小公倍数
目录 何为最小公倍数 题目要求 代码实现 方法一:暴力求解法(不推荐) 方法二:递乘试摸法(推荐) 何为最小公倍数 最小公倍数是指两个或者多个正整数(除了0以外)的最小的公共倍数…...
Langchain 对pdf,word,txt等不同文件的加载解析
项目中遇到各种数据资源想要加载近langchain构建本地知识ai系统,怎么加载对应的文件格式呢,一起研究下 引入Langchain from langchain.document_loaders import UnstructuredWordDocumentLoader,PyPDFium2Loader,DirectoryLoader,PyPDFLoader,TextLoad…...

BL201分布式I/O耦合器连接Profinet网络
钡铼技术的BL201分布式I/O耦合器是一个用于Profinet网络的设备,用于连接远程输入/输出(I/O)设备到控制系统,如可编程逻辑控制器(PLC),能够实现分布式的I/O连接和通信。 它支持标准Profinet IO …...

Pycharm 报错 Environment location directory is not empty 解
删除项目中ven文件夹(已存在的),然后再添加新的ven虚拟环境就可以了...
【Android】Intent基础用法及作用
文章目录 使用Intent在活动中穿梭组成显式Intent隐式Intent显式与隐式区别作用 活动间传递数据向下一个活动传递数据返回数据给上一个活动 使用Intent在活动中穿梭 Intent(意图)是一种重要的消息传递对象,用于在不同组件(如活动&…...

Web开发:ASP.NET CORE的后端小结(基础)
1.后端重定向到指定路由 public IActionResult Index(){return RedirectToAction("Index", "Main");//重定向>Main/Index} 【备注】如果在MainController的Index方法中return View();本质是 return View("Index"),返回和方法同名的…...
侧开知识点合集2
一、try .... catch.. AccessViolationException异常触发后,下列程序的输出结果为 static void Main(string[] args) { try { throw new AccessViolationException(); Console.WriteLine("error1"); } catch (Exception e) { Console.WriteLi…...
ARM/Linux嵌入式面经(十六):蔚来嵌入式一二三面面经
文章目录 static作用,局部static和全局static区别TCP三次握手Linux虚拟内存指针引用区别C++内存分区new/delete和malloc/free区别职业规划为什么选择蔚来介绍一下项目然后问我有没有内核级别开发经验,我说没有什么情况进入内核态一、主动式二、被动式三、其他方式注意事项示例…...

Apache BookKeeper 一致性协议解析
导语 Apache Pulsar 是一个多租户、高性能的服务间消息传输解决方案,支持多租户、低延时、读写分离、跨地域复制(GEO replication)、快速扩容、灵活容错等特性。Pulsar 存储层依托于 BookKeeper 组件,所以本文简单探讨一下 BookK…...
Solana的账户模型
Solana的账户模型与其他区块链平台(如以太坊)有所不同,其设计旨在提高性能和扩展性。以下是Solana账户模型的主要特点和工作原理: Solana账户模型概述 账户类型: 普通账户(User Accounts)&…...
iPython与Matplotlib:数据可视化的秘籍
iPython与Matplotlib:数据可视化的秘籍 前言 欢迎来到"iPython与Matplotlib:数据可视化的秘籍"教程!无论你是数据可视化新手还是希望提升技能的专业人士,这里都是你开始的地方。让我们开始这段数据可视化之旅吧&#…...
做一只勤劳的小蜜蜂
机缘 成为创作者的初心,对我而言,是一个融合了个人兴趣、职业成长以及对知识传播热爱的复杂而纯粹的情感交织。回顾这段旅程的起点,几个核心驱动力始终引领着我前行: 1、记录与反思:在职业生涯的早期,我遇…...

如何处理 PostgreSQL 中死锁的情况?
🍅关注博主🎗️ 带你畅游技术世界,不错过每一次成长机会!📚领书:PostgreSQL 入门到精通.pdf 文章目录 如何处理 PostgreSQL 中死锁的情况?一、认识死锁二、死锁的症状三、死锁的检测四、预防死锁…...

新版本 idea 创建不了 spring boot 2 【没有jkd8选项】
创建新项目 将地址换成如下 https://start.aliyun.com/...
linux系统和windows系统如何同步时间,服务器时间变动怎么同步
一、Linux系统时间同步 1. 使用NTP(网络时间协议) NTP是最常用的Linux系统时间同步方式。NTP通过连接到外部时间服务器(如原子钟或GPS接收器)来获取高精度的时间信息,并校准本地系统时间。 步骤: 安装N…...

Mac M1安装配置Hadoop+Flink SQL环境
Flink 1.18.1 Hadoop 3.4.0 一、准备工作 系统:Mac M1 (MacOS Sonoma 14.3.1) JDK:jdk1.8.0_381 (注意:尽量一定要用JDK8,少用高版本) Scala:2.12 JDK安装在本机的/opt/jdk1.8.0_381.jdk/C…...
【所谓生活】马太效应
简介 马太效应又称马太定律或两级分化现象。该效应描述的是在社会生活中,强者因为优势而获得更多机会,而弱者因劣势而失去机会,最终导致强者愈强、弱者愈弱的现象。这一概念最早由美国社会学家罗伯特莫顿于1968年提出,其名字来源…...

IDEA运行Tomcat出现乱码问题解决汇总
最近正值期末周,有很多同学在写期末Java web作业时,运行tomcat出现乱码问题,经过多次解决与研究,我做了如下整理: 原因: IDEA本身编码与tomcat的编码与Windows编码不同导致,Windows 系统控制台…...

(十)学生端搭建
本次旨在将之前的已完成的部分功能进行拼装到学生端,同时完善学生端的构建。本次工作主要包括: 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...

【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
Frozen-Flask :将 Flask 应用“冻结”为静态文件
Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是:将一个 Flask Web 应用生成成纯静态 HTML 文件,从而可以部署到静态网站托管服务上,如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...
Qt Http Server模块功能及架构
Qt Http Server 是 Qt 6.0 中引入的一个新模块,它提供了一个轻量级的 HTTP 服务器实现,主要用于构建基于 HTTP 的应用程序和服务。 功能介绍: 主要功能 HTTP服务器功能: 支持 HTTP/1.1 协议 简单的请求/响应处理模型 支持 GET…...

MySQL 8.0 OCP 英文题库解析(十三)
Oracle 为庆祝 MySQL 30 周年,截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始,将英文题库免费公布出来,并进行解析,帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...
LeetCode - 199. 二叉树的右视图
题目 199. 二叉树的右视图 - 力扣(LeetCode) 思路 右视图是指从树的右侧看,对于每一层,只能看到该层最右边的节点。实现思路是: 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

HDFS分布式存储 zookeeper
hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架,允许使用简单的变成模型跨计算机对大型集群进行分布式处理(1.海量的数据存储 2.海量数据的计算)Hadoop核心组件 hdfs(分布式文件存储系统)&a…...

Yolov8 目标检测蒸馏学习记录
yolov8系列模型蒸馏基本流程,代码下载:这里本人提交了一个demo:djdll/Yolov8_Distillation: Yolov8轻量化_蒸馏代码实现 在轻量化模型设计中,**知识蒸馏(Knowledge Distillation)**被广泛应用,作为提升模型…...