华为od机试真题 — 分披萨(Python)
创始人
2024-12-27 07:05:11
0

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 cache  n = 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, pizza     if t <= 1:         return 0      l, r = (l + n) % n, r % n      # “馋嘴”选择最大的一块     if pizza[l] >= pizza[r]:         l = (l - 1 + n) % n     else:         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 n     return 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 n       return fibonacci(n - 1) + fibonacci(n - 2)      print(fibonacci(50))    

相关练习题

题号题目难易
LeetCode 486486. 预测赢家中等
LeetCode 464464. 我能赢吗中等

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

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

相关内容

热门资讯

七分钟透明挂!约局吧软件有辅助... 七分钟透明挂!约局吧软件有辅助吗"德州ai机器人(原来真的有挂)-哔哩哔哩1、约局吧软件有辅助吗系统...
透视开发!微扑克这软件有问题吗... 透视开发!微扑克这软件有问题吗,云扑克有挂(其实真的有挂)1、ai机器人多个强度级别选择2、app发...
黑科技教程!微扑克专用辅助器(... 黑科技教程!微扑克专用辅助器(wepoke真的有挂)原来真的有挂(有挂科技)1、这是跨平台的微扑克专...
三分钟揭秘!wpk怎么检测伙牌... 三分钟揭秘!wpk怎么检测伙牌"wpk有辅助挂(其实真的有挂)-哔哩哔哩1、点击下载安装,微扑克wp...
透明挂教程!传奇扑克辅助(微扑... 透明挂教程!传奇扑克辅助(微扑克wpk透视辅助)原来真的有挂(有挂秘籍)1、每一步都需要思考,不同水...
透视内幕!云扑克有没有辅助挂,... 透视内幕!云扑克有没有辅助挂,线上德州ai机器人(其实真的有挂)是一款可以让一直输的玩家,快速成为一...
七分钟辅助挂!轰趴大菠萝十三水... 您好,轰趴大菠萝十三水有外挂吗这款游戏可以开挂的,确实是有挂的,需要了解加微【136704302】很...
2024新版教程!微扑克插件(... 2024新版教程!微扑克插件(微扑克ai辅助器苹果版)其实真的是有挂(有挂插件)是一款可以让一直输的...
7分钟辅助!德扑线上创建房间&... 7分钟辅助!德扑线上创建房间"德州免费辅助神器app(其实真的有挂)-哔哩哔哩1、德州免费辅助神器a...
透视揭秘!德州之星ai辅助,德... 透视揭秘!德州之星ai辅助,德州软件辅助(原来真的有挂);科技详细教程小薇《487309276》所有...