最新华为OD机试真题-贪吃的猴子(200分)

🍭 大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新 华为OD机试-D卷 的三语言AC题解

👏 感谢大家的订阅➕ 和 喜欢💗

📎在线评测链接

=>贪吃的猴子(200分) <=

🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁～

🍓OJ题目截图

🐒 贪吃的猴子

问题描述

LYA是一位热爱水果的小猴子。最近,她来到一个果园,发现里面种植了许多串香蕉,这些香蕉串排成一行。每串香蕉上有若干根香蕉,数量不等。

LYA打算采摘这些香蕉,但有一个规定:每次她只能从行的开头或末尾采摘一串香蕉,并且总共只能采摘 次。

LYA想知道,在这个限制下,她最多能采摘到多少根香蕉?

输入格式

第一行包含一个正整数 ,表示香蕉串的数量。

第二行包含 个正整数 ,其中 表示第 串香蕉上的香蕉根数。

第三行包含一个正整数 ,表示LYA能够采摘的次数。

输出格式

输出一个正整数,表示LYA最多能采摘到的香蕉根数。

样例输入 1

7
1 2 2 7 3 6 1  
3

样例输出 1

10

样例输入 2

3
1 2 3
3  

样例输出 2

6

样例输入 3

4
4 2 2 3
2

样例输出 3

7

数据范围

题解

我们可以使用贪心的思路来解决这个问题。首先,LYA采摘前 串香蕉,这样可以获得最大的初始分数。之后,每次她都应该采摘当前两端较大的那一串,以获得更多的香蕉。

具体做法是,我们用两个指针 和 分别指向剩余香蕉串的最左端和最右端。初始时,令 ,并计算前 串香蕉的总根数 ,将其作为当前最大分数 。之后,每次将 减去 并加上 ,更新 ,然后 和 分别向中间移动一步。重复这个过程,直到 和 相遇。

参考代码

• Python

n = int(input())
w = list(map(int, input().split()))
k = int(input())

total = sum(w[:k])
res = total
l, r = k - 1, n - 1

while l >= 0:
    total -= w[l]
    total += w[r]
    res = max(res, total)
    l -= 1
    r -= 1

print(res)

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] w = new int[n];
        for (int i = 0; i < n; i++) {
            w[i] = sc.nextInt();
        }
        int k = sc.nextInt();

        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += w[i];
        }
        int res = sum;

        int l = k - 1, r = n - 1;
        while (l >= 0) {
            sum -= w[l--];
            sum += w[r--];
            res = Math.max(res, sum);
        }

        System.out.println(res);
    }
}

• Cpp

#include <iostream>
#include <vector>

using namespace std;

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

    int sum = 0;
    for (int i = 0; i < k; i++) {
        sum += w[i];
    }
    int res = sum;

    int l = k - 1, r = n - 1;
    while (l >= 0) {
        sum -= w[l--];
        sum += w[r--];
        res = max(res, sum);
    }

    cout << res << endl;
    return 0;
}