华为OD机试真题 - 分披萨 (D卷,100分)

题目描述

"吃货"和"馋嘴"两人到披萨店点了一份铁盘（圆形）披萨，并嘱咐店员将披萨按放射状切成大小相同的偶数个小块。但是粗心的服务员将披萨切成了每块大小都完全不同奇数块，且肉眼能分辨出大小。

由于两人都想吃到最多的披萨，他们商量了一个他们认为公平的分法：从"吃货"开始，轮流取披萨。除了第一块披萨可以任意选取外，其他都必须从缺口开始选。

他俩选披萨的思路不同。"馋嘴"每次都会选最大块的披萨，而且"吃货"知道"馋嘴"的想法。

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

目录

题目描述

输入描述

输出描述

用例

题目解析

Java算法源码

JS算法源码

Python算法源码

C算法源码

华为机试有三道题目，第一道和第二道属于简单或中等题，分值为100分，第三道为中等或困难题，分值为200分。总分为400分，150分钟，机试是在牛客考试，练习的时候也可以在牛客网练习，提前熟悉操作

https://ac.nowcoder.com/acm/contest/5652/K

点击上方链接进入牛客练习界面，可以自定义题目，自定义输入、输出等等，华为OD真实机试环境，非其他第三方平台模拟。

输入描述

第 1 行为一个正整数奇数 N，表示披萨小块数量。

• 3 ≤ N < 500

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

• 1 ≤ i ≤ N

披萨小块从某一块开始，按照一个方向次序顺序编号为 1 ~ N

• 每块披萨的大小范围为 [1, 2147483647]

输出描述

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

用例

题目解析

1. 首先，将披萨小块按照大小从大到小排序。
2. 然后，"吃货"先选择最大的一块披萨。
3. "馋嘴"会选取剩下披萨中最大的一块。
4. "吃货"再选择剩下披萨中最大的一块。
5. "馋嘴"再次选取剩下披萨中最大的一块。
6. 重复步骤4和5，直到所有披萨都被选完。
7. 计算"吃货"分得的披萨大小的总和。

JS算法源码

  
const rl = require("readline").createInterface({ input: process.stdin });
const iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

(async () => {
  const n = parseInt(await readline());
  const pizza = [];
  for (let i = 0; i < n; i++) {
    pizza.push(parseInt(await readline()));
  }

  const check = (idx) => {
    if (idx < 0) {
      return n - 1;
    } else if (idx >= n) {
      return 0;
    }
    return idx;
  };

  const recursive = (l, r) => {
    if (pizza[l] > pizza[r]) {
      l = check(l - 1);
    } else {
      r = check(r + 1);
    }

    if (l === r) {
      return pizza[l];
    } else {
      return Math.max(
        recursive(check(l - 1), r) + pizza[l],
        recursive(l, check(r + 1)) + pizza[r]
      );
    }
  };

  let ans = 0;
  for (let i = 0; i < n; i++) {
    ans = Math.max(ans, recursive(check(i - 1), check(i + 1)) + pizza[i]);
  }

  console.log(ans);
})();

Java算法源码

import java.util.Scanner;

public class Main {
    static int[] pizza;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        pizza = new int[n];
        for (int i = 0; i < n; i++) {