当前位置： 首页 > article >正文

华为OD机试真题 - 分披萨 - 递归（Python/JS/C/C++ 2024 D卷 200分）

article 2025/3/7 3:24:20

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

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

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

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

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

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

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

二、输入描述

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

接下来的第 2 行到第 N+1 （共 N 行），每行为一个正整数，表示第i块披萨的大小， 1≤i≤N 。

披萨小块从某一块开始，按照一个方向次序顺序编号为 1 ~ N ,每块披萨的大小范围为[1,2147483647]。

三、输出描述

”吃货“能分得到的最大的披萨大小的总和。

四、测试用例

测试用例1：

1、输入

3
1
2
3

2、输出

4

3、说明

披萨被切成 3 块，大小分别为 1、2、3。
"吃货"最优策略是先选 3，然后 “馋嘴” 会选 2，最后 “吃货” 选 1。
因此，“吃货” 能获得的最大总和是 3 + 1 = 4。

测试用例2：

4、输入

7
10
20
30
40
50
60
70

5、输出

160

6、说明

披萨被切成 7 块，大小从 10 到 70。
“吃货” 的最优策略是选择 70、50、40，而 “馋嘴” 会选择 60、30、20。
“吃货” 获得的总和是 70 + 50 + 40 = 160。

五、解题思路

  1. 读取披萨块的数量 n 和每块披萨的大小。
  2. 使用哈希表存储中间结果以优化递归计算。
  3. 递归计算：
    • 定义一个递归函数 f(l, r, t)，表示在 l 到 r 的范围内，在 t 次轮换中“吃货”可以获得的最大披萨总和。
    • 基于剩余次数 t 的不同，计算“吃货”可能的选择。
    • 递归模拟“吃货”和“馋嘴”的选取过程。
  4. 结果计算：
    • 遍历所有可能的起始块，从每一块开始计算“吃货”能获得的最大总和。
    • 取所有计算结果的最大值。

虽然代码使用递归实现，但本质上是一个自顶向下的动态规划解法。每个子问题的解都可能被多次使用，我们通过缓存这些解来优化性能。

六、Python算法源码

def main():
    # 读取披萨块的数量
    n = int(input())
    pizza = list(map(int, input().split()))

    max_sum = 0
    # 尝试从每一块披萨开始，找出能获得最大总和的起始位置
    for i in range(n):
        # pizza[i] 是第一块选择的披萨，f(i-1, i+1, n-1) 计算剩余披萨的最优选择
        max_sum = max(max_sum, pizza[i] + f(i - 1, i + 1, n - 1, pizza, {}))

    # 输出"吃货"能获得的最大披萨总和
    print(max_sum)

def f(l, r, t, pizza, cache):
    # 基本情况：如果剩余次数小于等于1，意味着这是"馋嘴"的最后一次选择，"吃货"无法再获得披萨
    if t <= 1:
        return 0

    # 处理循环边界，确保l和r在有效范围内
    l = (l + n) % n
    r = r % n

    # 检查缓存，如果之前计算过这个状态，直接返回缓存的结果
    key = (l, r, t)
    if key in cache:
        return cache[key]

    # 模拟"馋嘴"的选择：总是选择较大的一块
    if pizza[l] >= pizza[r]:
        l = (l - 1 + n) % n  # "馋嘴"选择了左边的披萨，左边界向左移动
    else:
        r = (r + 1) % n  # "馋嘴"选择了右边的披萨，右边界向右移动

    # 计算"吃货"两种选择的结果：
    # 选择左边的披萨
    s1 = pizza[l] + f((l - 1 + n) % n, r, t - 2, pizza, cache)
    # 选择右边的披萨
    s2 = pizza[r] + f(l, (r + 1) % n, t - 2, pizza, cache)

    # 选择较大的结果
    result = max(s1, s2)
    # 将结果存入缓存
    cache[key] = result
    return result

if __name__ == "__main__":
    main()

七、JavaScript算法源码

function main() {
    const fs = require('fs');
    const input = fs.readFileSync('/dev/stdin', 'utf8').trim().split('\n');
    
    const n = parseInt(input[0]);
    const pizza = input[1].split(' ').map(Number);

    let maxSum = 0;
    const cache = new Map();

    // 尝试从每一块披萨开始，找出能获得最大总和的起始位置
    for (let i = 0; i < n; i++) {
        maxSum = Math.max(maxSum, pizza[i] + f(i - 1, i + 1, n - 1, pizza, cache));
    }

    // 输出"吃货"能获得的最大披萨总和
    console.log(maxSum);
}

function f(l, r, t, pizza, cache) {
    const n = pizza.length;

    // 基本情况：如果剩余次数小于等于1，"吃货"无法再获得披萨
    if (t <= 1) {
        return 0;
    }

    // 处理循环边界，确保l和r在有效范围内
    l = (l + n) % n;
    r = r % n;

    // 检查缓存，如果之前计算过这个状态，直接返回缓存的结果
    const key = `${l},${r},${t}`;
    if (cache.has(key)) {
        return cache.get(key);
    }

    // 模拟"馋嘴"的选择：总是选择较大的一块
    if (pizza[l] >= pizza[r]) {
        l = (l - 1 + n) % n;  // "馋嘴"选择了左边的披萨，左边界向左移动
    } else {
        r = (r + 1) % n;  // "馋嘴"选择了右边的披萨，右边界向右移动
    }

    // 计算"吃货"两种选择的结果：
    const s1 = pizza[l] + f((l - 1 + n) % n, r, t - 2, pizza, cache);
    const s2 = pizza[r] + f(l, (r + 1) % n, t - 2, pizza, cache);

    // 选择较大的结果
    const result = Math.max(s1, s2);
    // 将结果存入缓存
    cache.set(key, result);
    return result;
}

// 如果在Node.js环境中运行，调用main函数
main();

八、C算法源码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 100

int n;
int pizza[MAX_N];
int cache[MAX_N][MAX_N][MAX_N];

// 初始化缓存
void init_cache() {
    for (int i = 0; i < MAX_N; i++) {
        for (int j = 0; j < MAX_N; j++) {
            for (int k = 0; k < MAX_N; k++) {
                cache[i][j][k] = -1;
            }
        }
    }
}

int f(int l, int r, int t);

// 主函数
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &pizza[i]);
    }

    int maxSum = 0;
    init_cache();

    // 尝试从每一块披萨开始，找出能获得最大总和的起始位置
    for (int i = 0; i < n; i++) {
        maxSum = (pizza[i] + f((i - 1 + n) % n, (i + 1) % n, n - 1) > maxSum) ? 
                 (pizza[i] + f((i - 1 + n) % n, (i + 1) % n, n - 1)) : maxSum;
    }

    printf("%d\n", maxSum);
    return 0;
}

// 递归函数，计算在给定状态下"吃货"能获得的最大披萨总和
int f(int l, int r, int t) {
    if (t <= 1) {
        return 0;
    }

    l = (l + n) % n;
    r = r % n;

    if (cache[l][r][t] != -1) {
        return cache[l][r][t];
    }

    if (pizza[l] >= pizza[r]) {
        l = (l - 1 + n) % n;
    } else {
        r = (r + 1) % n;
    }

    int s1 = pizza[l] + f((l - 1 + n) % n, r, t - 2);
    int s2 = pizza[r] + f(l, (r + 1) % n, t - 2);

    cache[l][r][t] = (s1 > s2) ? s1 : s2;
    return cache[l][r][t];
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>

using namespace std;

#define MAX_N 100

int n;
vector<int> pizza(MAX_N);
int cache[MAX_N][MAX_N][MAX_N];

// 初始化缓存
void init_cache() {
    memset(cache, -1, sizeof(cache));
}

int f(int l, int r, int t);

// 主函数
int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> pizza[i];
    }

    int maxSum = 0;
    init_cache();

    // 尝试从每一块披萨开始，找出能获得最大总和的起始位置
    for (int i = 0; i < n; i++) {
        maxSum = max(maxSum, pizza[i] + f((i - 1 + n) % n, (i + 1) % n, n - 1));
    }

    cout << maxSum << endl;
    return 0;
}

// 递归函数，计算在给定状态下"吃货"能获得的最大披萨总和
int f(int l, int r, int t) {
    if (t <= 1) {
        return 0;
    }

    l = (l + n) % n;
    r = r % n;

    if (cache[l][r][t] != -1) {
        return cache[l][r][t];
    }

    if (pizza[l] >= pizza[r]) {
        l = (l - 1 + n) % n;
    } else {
        r = (r + 1) % n;
    }

    int s1 = pizza[l] + f((l - 1 + n) % n, r, t - 2);
    int s2 = pizza[r] + f(l, (r + 1) % n, t - 2);

    cache[l][r][t] = max(s1, s2);
    return cache[l][r][t];
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

在这里插入图片描述


http://www.kler.cn/a/299268.html

相关文章：

  • 怎么利用智能电销机器人改善您的销售效率
  • 105页PPT：华为ISC集成供应链变革、模式与方法解析
  • 使用C#自动创建windows任务计划程序，并使用微软API文档教程
  • python爬虫基础:了解html
  • 如何用matlab灵活控制feko的求解
  • 根据NVeloDocx Word模板引擎生成Word（三）
  • C# 路径操作
  • CISC 和 RISC 架构的对比
  • 本地Linux服务器使用docker搭建DashDot并实现公网实时监测服务器信息
  • Linux 基础命令-文件与目录操作
  • python使用xpath获取html中的所有链接
  • 箱包潮湿发霉怎么处理 箱包发霉处理不长霉
  • Linux线程概念
  • Python VTK 绘制等高线初步
  • Linux学习-ELK(一)
  • VMware-Ubuntu Server安装教程
  • hive表格统计信息不准确
  • ISP面试准备2
  • HarmonyOS---应用测试概述
  • Linux 上安装 PostgreSQL