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

avatar
作者
猴君
阅读量:2

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++合集

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

广告一刻

为您即时展示最新活动产品广告消息,让您随时掌握产品活动新动态!