分披萨 | 您所在的位置:网站首页 › 披萨考试中国第几名 › 分披萨 |
分披萨 - 华为OD统一考试(C卷)
OD统一考试(C卷) 分值: 100分 题解: Java / Python / C++ “吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨,并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。 但是粗心服务员将披萨切成了每块大小都完全不同奇数块,且肉眼能分辨出大小。 由于两人都想吃到最多的披萨,他们商量了一个他们认为公平的分法:从“吃货”开始,轮流取披萨。 除了第-块披萨可以任意选取以外,其他都必须从缺口开始选。 他俩选披萨的思路不同。 “馋嘴”每次都会选最大块的拨萨,而且“吃货”知道“馋嘴”的想法。 已知披萨小块的数量以及每块的大小,求“吃货”能分得的最大的披萨大小的总和。 输入描述第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 可能存在多种拿法,以上只是其中一种。 题解解题思路: 记忆化搜索算法,计算“吃货”在每一轮中的最佳选择。使用二维缓存数组 cache 来存储中间结果,避免重复计算。 代码描述: 定义 get_max_sum 函数,表示在给定可选的左右边界索引和剩余披萨块数,吃货能分到的最大披萨总和。 在 get_max_sum 函数中,首先对左右边界进行调整(避免数组越界),“馋嘴”选择最大的一块。 使用递归计算( “吃货”)两种情况下的最大总和:选择左边界块和选择右边界块。 返回最优解并将结果缓存到 cache 中,避免重复计算。 在主函数中,尝试每种选择,然后取结果最大的值。 Java import java.util.Arrays; import java.util.Scanner; /** * @author code5bug */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] p = new int[n]; for (int i = 0; i < n; i++) p[i] = in.nextInt(); Solution solution = new Solution(); System.out.println(solution.solve(p, n)); } } class Solution { int n; int[] p; long[][] cache; /** * @param l, r: 可以选择的两端索引下标 * @param t: 剩余的披萨块数 * @return: 返回 “吃货” 最优选择时可以分到的披萨总和 */ private long getMaxSum(int l, int r, int t) { if (t = p[r]) { l = (l - 1 + n) % n; } else { r = (r + 1) % n;剩余60%内容,订阅专栏后可继续查看/也可单篇购买 2024华为OD机试真题题解 文章被收录于专栏华为OD机考(C卷、D卷)算法题库(绝对都是原题),帮助你上岸华为(已经不少小伙伴成功上岸)。提供Java、Python、C++ 三种语言的解法。每篇文章都有详细的解题步骤、代码注释详细及相关知识点的练习题。有问题,随时解答。 从 2024年4月24开始,考的都是华为OD统一考试(D卷),据已经参加D卷考试的同学反馈D卷和C卷是一样的,如果发现新题会及时更新。 |
CopyRight 2018-2019 实验室设备网 版权所有 |