贪吃的猴子 – 华为OD统一考试(C卷)

OD统一考试(C卷)

分值: 200分

题解: Java / Python / C++

alt

题目描述

一只贪吃的猴子,来到一个果园,发现许多串香蕉排成一行,每串香蕉上有若干根香蕉。每串香蕉的根数由数组numbers给出。猴子获取香蕉,每次都只能从行的开头或者末尾获取,并且只能获取N次,求猴子最多能获取多少根香蕉。

输入描述

第一行为数组numbers的长度

第二行为数组numbers的值每个数字通过空格分开

第三行输入为N,表示获取的次数

输出描述

按照题目要求能获取的最大数值

示例1

输入
7
1 2 2 7 3 6 1
3

输出
10

示例2

输入
3
1 2 3
3

输出
6

说明
全部获取所有的香蕉,因此最终根数为1+2+3 = 6

示例3

输入
4
4 2 2 3
2

输出
7

说明
第一次获取香蕉为行的开头,第二次获取为行的末尾,因此最终根数为4+3 =7

备注

1<= numbers.length <= 100000

1<= numbers <= 100

1 <= N <= numbers.length

题解

这是一道数组和双指针的题目,需要通过双指针的方式在数组中找到最优解。

解题思路:

双指针的思路是通过两个指针(在这里是 lr)从两端向中间移动,通过不断的调整两边的元素选取个数,找到最佳结果。在这个问题中,通过调整左右两边的选取次数,计算获取香蕉的总数。

C++

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> numbers(n);
    for(int i=0; i<n; i++) cin >> numbers[i];

    int N;
    cin >> N;
    int tot = 0;
    for(int i=0; i<N; i++) tot += numbers[i];

    int rs = tot;

    int l = N-1, r = n-1;
    while(l >= 0) {
        tot += numbers[r--] - numbers[l--];
        rs = max(rs, tot);
    }

    cout << rs << endl;

    return 0;
}

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] numbers = Arrays.stream(new int[n]).map(i -> in.nextInt()).toArray();
        int N = in.nextInt();

        // 左边选N个, 右侧选0个
        int tot = Arrays.stream(numbers, 0, N).sum();

        int rs = tot;
        int l = N - 1, r = n - 1;

        // 不断的尝试调整两边的元素选取个数, 找到最佳结果
        while (l >= 0) {
            tot += numbers[r--] - numbers[l--];
            rs = Math.max(rs, tot);
        }
        System.out.println(rs);
    }
}

以上题解给我一些总结性的描述,从以下几点方面: 题目类型,解题思路,代码大致描述,时间复杂度,空间复杂度,及相关知识点

Python

n = int(input())
numbers = list(map(int, input().split()))
N = int(input())

tot = sum(numbers[i] for i in range(N))
rs = tot

r = n - 1
for l in range(N-1, -1, -1):
    tot += numbers[r] - numbers[l]
    rs = max(rs, tot)
    r -= 1

print(rs)

🙏整理题解不易, 如果有帮助到您,请给点个赞 ‍❤️‍ 和收藏 ⭐,让更多的人看到。🙏🙏🙏

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>