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

2024-07-19 15:42:24
开发
23

alt

题目描述

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

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

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

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

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

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

输入描述

第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 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))