当前位置: 首页 > news >正文

华为od机试真题 — 分披萨(Python)

alt

题目描述

“吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨,并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。

但是粗心服务员将披萨切成了每块大小都完全不同奇数块,且肉眼能分辨出大小。

由于两人都想吃到最多的披萨,他们商量了一个他们认为公平的分法:从“吃货”开始,轮流取披萨。

除了第-块披萨可以任意选取以外,其他都必须从缺口开始选。 他俩选披萨的思路不同。

“馋嘴”每次都会选最大块的拨萨,而且“吃货”知道“馋嘴”的想法。

已知披萨小块的数量以及每块的大小,求“吃货”能分得的最大的披萨大小的总和。

输入描述

第1行为一个正整数奇数 N ,表示披萨小块数量。其中 3 ≤ N< 500

接下来的第 2 行到第 N+1 (共 N 行),每行为一个正整数,表示第i块披萨的大小, 1≤iN

披萨小块从某一块开始,按照一个方向次序顺序编号为 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
可能存在多种拿法,以上只是其中一种。

解题思路

解题思路

  1. 记忆化搜索:定义一个递归函数 f(l, r, t) 来表示从区间 [l, r] 里,“吃货”能分得的最大披萨大小的总和。这里 lr 分别表示区间的左边界和右边界,t 表示剩余的次数。
  2. 贪心选择:每次“馋嘴”都会选择当前区间内最大的披萨块,这会影响到下一步“吃货”的选择。因此,我们需要在“吃货”选择之前模拟“馋嘴”的贪心选择,以确保“吃货”能得到最大总和。
  3. 递归处理:递归地缩小问题规模,通过模拟“吃货”在每一步的选择,并记录下最优结果。

代码描述

  1. 输入处理:读取输入的披萨块数量 n 和每块披萨的大小。
  2. 缓存优化:使用 functools.cache 来缓存递归结果,避免重复计算。
  3. 递归函数 f
    • 参数:l 为左边界,r 为右边界,t 为剩余次数。
    • 基本情况:如果剩余次数 t 小于等于1,则返回0。
    • 贪心选择:模拟“馋嘴”选择当前区间内的最大披萨块,更新 lr
    • 动态规划选择:计算“吃货”选择左边界 l 或右边界 r 时的最大总和,并返回其中较大的值。
  4. 主逻辑:通过遍历每块披萨,计算“吃货”从该块披萨开始能得到的最大总和。

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 486486. 预测赢家中等
LeetCode 464464. 我能赢吗中等

2024华为OD机试(C卷+D卷)最新题库【超值优惠】Java/Python/C++合集

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

相关文章:

华为od机试真题 — 分披萨(Python)

题目描述 “吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨&#xff0c;并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。 但是粗心服务员将披萨切成了每块大小都完全不同奇数块&#xff0c;且肉眼能分辨出大小。 由于两人都想吃到最多的披萨&#xff0c;他们商量…...

ubuntu22.04 安装boost

下载boost压缩包&#xff0c;我这里上传了一份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步完成后&#xff0c;相关…...

基于JAVA+SpringBoot+uniapp的心理小程序(小程序版本)

✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、Jsp、SpringCloud、Layui、Echarts图表、Nodejs、爬…...

C语言 ——— 输入两个正整数,求出最小公倍数

目录 何为最小公倍数 题目要求 代码实现 方法一&#xff1a;暴力求解法&#xff08;不推荐&#xff09; 方法二&#xff1a;递乘试摸法&#xff08;推荐&#xff09; 何为最小公倍数 最小公倍数是指两个或者多个正整数&#xff08;除了0以外&#xff09;的最小的公共倍数…...

Langchain 对pdf,word,txt等不同文件的加载解析

项目中遇到各种数据资源想要加载近langchain构建本地知识ai系统&#xff0c;怎么加载对应的文件格式呢&#xff0c;一起研究下 引入Langchain from langchain.document_loaders import UnstructuredWordDocumentLoader,PyPDFium2Loader,DirectoryLoader,PyPDFLoader,TextLoad…...

BL201分布式I/O耦合器连接Profinet网络

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

Pycharm 报错 Environment location directory is not empty 解

删除项目中ven文件夹&#xff08;已存在的&#xff09;&#xff0c;然后再添加新的ven虚拟环境就可以了...

【Android】Intent基础用法及作用

文章目录 使用Intent在活动中穿梭组成显式Intent隐式Intent显式与隐式区别作用 活动间传递数据向下一个活动传递数据返回数据给上一个活动 使用Intent在活动中穿梭 Intent&#xff08;意图&#xff09;是一种重要的消息传递对象&#xff0c;用于在不同组件&#xff08;如活动&…...

Web开发:ASP.NET CORE的后端小结(基础)

1.后端重定向到指定路由 public IActionResult Index(){return RedirectToAction("Index", "Main");//重定向>Main/Index} 【备注】如果在MainController的Index方法中return View();本质是 return View("Index")&#xff0c;返回和方法同名的…...

侧开知识点合集2

一、try .... catch.. AccessViolationException异常触发后&#xff0c;下列程序的输出结果为 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 是一个多租户、高性能的服务间消息传输解决方案&#xff0c;支持多租户、低延时、读写分离、跨地域复制&#xff08;GEO replication&#xff09;、快速扩容、灵活容错等特性。Pulsar 存储层依托于 BookKeeper 组件&#xff0c;所以本文简单探讨一下 BookK…...

Solana的账户模型

Solana的账户模型与其他区块链平台&#xff08;如以太坊&#xff09;有所不同&#xff0c;其设计旨在提高性能和扩展性。以下是Solana账户模型的主要特点和工作原理&#xff1a; Solana账户模型概述 账户类型&#xff1a; 普通账户&#xff08;User Accounts&#xff09;&…...

iPython与Matplotlib:数据可视化的秘籍

iPython与Matplotlib&#xff1a;数据可视化的秘籍 前言 欢迎来到"iPython与Matplotlib&#xff1a;数据可视化的秘籍"教程&#xff01;无论你是数据可视化新手还是希望提升技能的专业人士&#xff0c;这里都是你开始的地方。让我们开始这段数据可视化之旅吧&#…...

做一只勤劳的小蜜蜂

机缘 成为创作者的初心&#xff0c;对我而言&#xff0c;是一个融合了个人兴趣、职业成长以及对知识传播热爱的复杂而纯粹的情感交织。回顾这段旅程的起点&#xff0c;几个核心驱动力始终引领着我前行&#xff1a; 1、记录与反思&#xff1a;在职业生涯的早期&#xff0c;我遇…...

如何处理 PostgreSQL 中死锁的情况?

&#x1f345;关注博主&#x1f397;️ 带你畅游技术世界&#xff0c;不错过每一次成长机会&#xff01;&#x1f4da;领书&#xff1a;PostgreSQL 入门到精通.pdf 文章目录 如何处理 PostgreSQL 中死锁的情况&#xff1f;一、认识死锁二、死锁的症状三、死锁的检测四、预防死锁…...

新版本 idea 创建不了 spring boot 2 【没有jkd8选项】

创建新项目 将地址换成如下 https://start.aliyun.com/...

linux系统和windows系统如何同步时间,服务器时间变动怎么同步

一、Linux系统时间同步 1. 使用NTP&#xff08;网络时间协议&#xff09; NTP是最常用的Linux系统时间同步方式。NTP通过连接到外部时间服务器&#xff08;如原子钟或GPS接收器&#xff09;来获取高精度的时间信息&#xff0c;并校准本地系统时间。 步骤&#xff1a; 安装N…...

Mac M1安装配置Hadoop+Flink SQL环境

Flink 1.18.1 Hadoop 3.4.0 一、准备工作 系统&#xff1a;Mac M1 (MacOS Sonoma 14.3.1) JDK&#xff1a;jdk1.8.0_381 &#xff08;注意&#xff1a;尽量一定要用JDK8&#xff0c;少用高版本&#xff09; Scala&#xff1a;2.12 JDK安装在本机的/opt/jdk1.8.0_381.jdk/C…...

【所谓生活】马太效应

简介 马太效应又称马太定律或两级分化现象。该效应描述的是在社会生活中&#xff0c;强者因为优势而获得更多机会&#xff0c;而弱者因劣势而失去机会&#xff0c;最终导致强者愈强、弱者愈弱的现象。这一概念最早由美国社会学家罗伯特莫顿于1968年提出&#xff0c;其名字来源…...

日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻

在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

Python爬虫实战:研究feedparser库相关技术

1. 引言 1.1 研究背景与意义 在当今信息爆炸的时代,互联网上存在着海量的信息资源。RSS(Really Simple Syndication)作为一种标准化的信息聚合技术,被广泛用于网站内容的发布和订阅。通过 RSS,用户可以方便地获取网站更新的内容,而无需频繁访问各个网站。 然而,互联网…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

起重机起升机构的安全装置有哪些?

起重机起升机构的安全装置是保障吊装作业安全的关键部件&#xff0c;主要用于防止超载、失控、断绳等危险情况。以下是常见的安全装置及其功能和原理&#xff1a; 一、超载保护装置&#xff08;核心安全装置&#xff09; 1. 起重量限制器 功能&#xff1a;实时监测起升载荷&a…...

基于Uniapp的HarmonyOS 5.0体育应用开发攻略

一、技术架构设计 1.混合开发框架选型 &#xff08;1&#xff09;使用Uniapp 3.8版本支持ArkTS编译 &#xff08;2&#xff09;通过uni-harmony插件调用原生能力 &#xff08;3&#xff09;分层架构设计&#xff1a; graph TDA[UI层] -->|Vue语法| B(Uniapp框架)B --&g…...