西安网站备案,国外网站能否做百科参考资料,织梦系统怎么做单页网站,高端自适应网站设计华为OD机试 2024C卷题库疯狂收录中#xff0c;刷题点这里 专栏导读
本专栏收录于《华为OD机试#xff08;JAVA#xff09;真题#xff08;A卷B卷C卷#xff09;》。
刷的越多#xff0c;抽中的概率越大#xff0c;每一题都有详细的答题思路、详细的代码注释、样例测试… 华为OD机试 2024C卷题库疯狂收录中刷题点这里 专栏导读
本专栏收录于《华为OD机试JAVA真题A卷B卷C卷》。
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
一、题目描述
“吃货”和“馋嘴”两人到披萨店点了一份铁盘(圆形)披萨并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。
但是粗心服务员将披萨切成了每块大小都完全不同奇数块且肉眼能分辨出大小。
由于两人都想吃到最多的披萨他们商量了一个他们认为公平的分法:从“吃货”开始轮流取披萨。
除了第-块披萨可以任意选取以外其他都必须从缺口开始选。 他俩选披萨的思路不同。
“馋嘴”每次都会选最大块的拨萨而且“吃货”知道“馋嘴”的想法。
已知披萨小块的数量以及每块的大小求“吃货”能分得的最大的披萨大小的总和。
二、输入描述
第1行为一个正整数奇数 N 表示披萨小块数量。其中 3 ≤ N 500
接下来的第 2 行到第 N1 共 N 行每行为一个正整数表示第i块披萨的大小 1≤i≤N 。
披萨小块从某一块开始按照一个方向次序顺序编号为 1 ~ N ,每块披萨的大小范围为[1,2147483647]。
三、输出描述
”吃货“能分得到的最大的披萨大小的总和。
四、解题思路
将输入的披萨小块按照大小进行排序。使用动态规划的方法来解决这个问题。我们可以定义一个数组 dp[i] 表示从第 i 块披萨开始“吃货”能分得的最大披萨大小的总和。对于每一块披萨我们可以选择取或者不取。如果我们选择取这块披萨那么“吃货”能分得的总和就是 dp[i-1] pizza[i]其中 pizza[i]第 i 块披萨的大小。如果我们选择不取这块披萨那么“吃货”能分得的总和就是 dp[i-2] pizza[i]。最后找到 dp[N]、dp[N-1]、…、dp[1] 中的最大值即为“吃货”能分得的最大披萨大小的总和。
五、Java算法源码
public class Test02 {public static void main(String[] args) {Scanner sc new Scanner(System.in);int N sc.nextInt();int[] pizza new int[N];for (int i 0; i N; i) {pizza[i] sc.nextInt();}sc.close();// 对披萨小块按照大小进行排序Arrays.sort(pizza);// 初始化动态规划数组long[] dp new long[N];dp[0] pizza[0];dp[1] Math.max(pizza[0], pizza[1]);// 动态规划求解for (int i 2; i N; i) {dp[i] Math.max(dp[i - 1], dp[i - 2] pizza[i]);}// 输出结果System.out.println(dp[N - 1]);}
}六、效果展示
1、输入
5 8 2 10 5 7
2、输出
19
3、说明
此例子中有 5 块披萨。每块大小依次为 8 、2 、10 、5 、7。
按照如下顺序拿披萨可以使”吃货拿到最多披萨:
“吃货”拿大小为 10 的披萨“馋嘴”拿大小为5的披萨“吃货”拿大小为7 的披萨“馋嘴”拿大小为 8 的披萨”吃货“拿大小为2 的披萨
至此披萨瓜分完毕”吃货“拿到的披萨总大小为 107219 下一篇华为OD机试 - 简易内存池 - 逻辑分析Java 2024 C卷 200分
本文收录于华为OD机试JAVA真题A卷B卷C卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
