华为OD机考双机位B卷 - 贪吃的猴子 （Java Python JS C/C++ GO ）

最新华为上机考试

真题目录：点击查看目录
华为OD面试真题精选：点击立即查看
2025华为od机试双机位B卷

题目描述

只贪吃的猴子，来到一个果园，发现许多串香蕉排成一行，每串香蕉上有若干根香蕉。每串香蕉的根数由数组numbers给出。

猴子获取香蕉，每次都只能从行的开头或者末尾获取，并且只能获取N次，求猴子最多能获取多少根香蕉。

输入描述

第一行为数组numbers的长度

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

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

备注：

• 1 ≤ numbers.length ≤ 100000
• 1 ≤ numbers ≤ 100
• 1 ≤ N ≤ numbers.length

输出描述

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

用例

输入

7 1 2 2 7 3 6 1 3

输出

10

说明

第一次获取香蕉，无论是从行的开头或者末尾获取，得到的香蕉根数目为1, 但是，从行末尾获取能获取到最优的策略，后面可以直接得到香蕉根数目6和3。因此最终根数为1+6+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解释题目：

1 2 2 7 3 6 1

每次都是开头或末尾：

第一次：开头和末尾都是1，

第二次：

如果我们第一次是开头，此时数字就是【2 2 7 3 6 1】，开头就是2 结尾就是1。

如果我们第一次是结尾，此时数字就是【1 2 2 7 3 6 】，开头就是1 结尾就是6。

这样我们就会发现第一次选末尾 第二次选末尾，第三次仍然选末尾，这样就是最多根。

我们以用例3解释题目：

4 2 2 3

我们一眼可以看出，第一次选开头 第二次选末尾。

从这两个例子，我们好像找不到啥规律啊，但是我们把视角转到选不到的桃子，你会发现，无论每次是选开头还是结尾，选不到的桃子永远是连续的，对不对！！！ 再转念一想，我们把数组看成一个环，选中的开头和结尾是不是也就是连续的啊。这样我们自然而然就想到了**【滑动窗口】**

试验了两种解法，一种的选中的是连续的，一种是未选中的连续（选中的就是数组-未选中的）。我觉得从未选中的角度去解题比较简单。

最终就转换为：求某个连续的区间是的总和最小。

解题思路

1. 读取输入，包括数组长度、数组元素（每串香蕉的数量），以及猴子可以获取的次数。
2. 计算数组中所有香蕉的总数。
3. 如果猴子可以获取的次数等于数组长度，即猴子可以拿走所有的香蕉，直接返回总数。
4. **计算猴子不能拿走的连续香蕉串的最小总数。**这是通过滑动窗口实现的，窗口大小为数组长度 - N。
5. 初始化滑动窗口的和为窗口内的第一段连续香蕉串的和。
6. 滑动窗口，每次向右移动一位，更新窗口和，并记录最小的窗口和。
7. 猴子能获取的最大香蕉数是总和减去最小窗口和。

模拟计算过程

给定输入：

数组长度：7 香蕉数量：1 2 2 7 3 6 1 猴子次数：3

1. 计算香蕉总数：1 + 2 + 2 + 7 + 3 + 6 + 1 = 22
2. 窗口大小：7 - 3 = 4
3. 初始化窗口和：1 + 2 + 2 + 7 = 12
4. 滑动窗口并计算最小窗口和：
   • 窗口[2, 2, 7, 3]和为14，最小和仍为12
   • 窗口[2, 7, 3, 6]和为18，最小和仍为12
   • 窗口[7, 3, 6, 1]和为17，最小和仍为12
5. 猴子能获取的最大香蕉数：总和 - 最小窗口和 = 22 - 12 = 10

因此，猴子能获取的最大香蕉数为10。

C++

#include<iostream>#include<vector>#include<climits>using namespace std;// 计算猴子能获取的最大香蕉数intmaxBananas(constvector<int>&numbers,intN){inttotal=0;// 初始化数组总和为0// 计算数组中所有香蕉的总数for(intnumber:numbers){total+=number;}// 如果N等于数组长度，猴子可以拿走所有的香蕉if(N==numbers.size()){returntotal;}intminWindowSum=INT_MAX;// 初始化最小窗口和为最大整数值intcurrentWindowSum=0;// 初始化当前窗口和为0intwindowSize=numbers.size()-N;// 计算窗口大小// 初始化窗口的和for(inti=0;i<windowSize;i++){currentWindowSum+=numbers[i];}minWindowSum=currentWindowSum;// 将当前窗口和赋值给最小窗口和// 通过滑动窗口计算最小窗口和for(inti=windowSize;i<numbers.size();i++){// 窗口滑动，加上新进入窗口的元素，减去离开窗口的元素currentWindowSum+=numbers[i]-numbers[i-windowSize];// 更新最小窗口和minWindowSum=min(minWindowSum,currentWindowSum);}// 猴子能获取的最大香蕉数是总和减去最小窗口和returntotal-minWindowSum;}intmain(){intlen;// 读取数组长度cin>>len;vector<int>numbers(len);// 创建数组存储每串香蕉的数量for(inti=0;i<len;i++){cin>>numbers[i];// 循环读取每串香蕉的数量}intN;// 读取猴子可以获取的次数cin>>N;cout<<maxBananas(numbers,N)<<endl;// 输出猴子能获取的最大香蕉数return0;}

Java

importjava.util.Scanner;publicclassMain{publicstaticvoidmain(String[]args){Scannerscanner=newScanner(System.in);intlen=scanner.nextInt();// 读取数组长度int[]numbers=newint[len];// 创建数组存储每串香蕉的数量for(inti=0;i<len;i++){numbers[i]=scanner.nextInt();// 循环读取每串香蕉的数量}intN=scanner.nextInt();// 读取猴子可以获取的次数System.out.println(maxBananas(numbers,N));// 输出猴子能获取的最大香蕉数}// 定义方法计算猴子能获取的最大香蕉数privatestaticintmaxBananas(int[]numbers,intN){inttotal=0;// 初始化数组总和为0// 计算数组中所有香蕉的总数for(intnumber:numbers){total+=number;}// 如果N等于数组长度，猴子可以拿走所有的香蕉if(N==numbers.length){returntotal;}intminWindowSum=Integer.MAX_VALUE;// 初始化最小窗口和为最大整数值intcurrentWindowSum=0;// 初始化当前窗口和为0intwindowSize=numbers.length-N;// 计算窗口大小// 初始化窗口的和for(inti=0;i<windowSize;i++){currentWindowSum+=numbers[i];}minWindowSum=currentWindowSum;// 将当前窗口和赋值给最小窗口和// 通过滑动窗口计算最小窗口和for(inti=windowSize;i<numbers.length;i++){// 窗口滑动，加上新进入窗口的元素，减去离开窗口的元素currentWindowSum+=numbers[i]-numbers[i-windowSize];// 更新最小窗口和minWindowSum=Math.min(minWindowSum,currentWindowSum);}// 猴子能获取的最大香蕉数是总和减去最小窗口和returntotal-minWindowSum;}}

javaScript

// 使用Node.js的readline模块来处理输入constreadline=require('readline');constrl=readline.createInterface({input:process.stdin,output:process.stdout});// 读取输入rl.on('line',(len)=>{len=parseInt(len);rl.on('line',(numbers)=>{numbers=numbers.split(' ').map(Number);rl.on('line',(N)=>{N=parseInt(N);console.log(maxBananas(numbers,N));// 输出猴子能获取的最大香蕉数rl.close();});});});// 计算猴子能获取的最大香蕉数functionmaxBananas(numbers,N){lettotal=numbers.reduce((acc,val)=>acc+val,0);// 计算数组中所有香蕉的总数if(N===numbers.length){returntotal;// 如果N等于数组长度，猴子可以拿走所有的香蕉}letminWindowSum=Infinity;// 初始化最小窗口和为无穷大letcurrentWindowSum=0;// 初始化当前窗口和为0letwindowSize=numbers.length-N;// 计算窗口大小for(leti=0;i<windowSize;i++){currentWindowSum+=numbers[i];}minWindowSum=currentWindowSum;for(leti=windowSize;i<numbers.length;i++){currentWindowSum+=numbers[i]-numbers[i-windowSize];minWindowSum=Math.min(minWindowSum,currentWindowSum);}returntotal-minWindowSum;// 猴子能获取的最大香蕉数是总和减去最小窗口和}

Python

importsys# 计算猴子能获取的最大香蕉数的函数defmax_bananas(numbers,N):# 计算数组中所有香蕉的总数total=sum(numbers)# 如果N等于数组长度，猴子可以拿走所有的香蕉ifN==len(numbers):returntotal# 初始化最小窗口和为无穷大min_window_sum=float('inf')# 初始化当前窗口和为0current_window_sum=0# 计算窗口大小window_size=len(numbers)-N# 初始化当前窗口的和foriinrange(window_size):current_window_sum+=numbers[i]min_window_sum=current_window_sum# 通过滑动窗口计算最小窗口和foriinrange(window_size,len(numbers)):# 窗口滑动，加上新进入窗口的元素，减去离开窗口的元素current_window_sum+=numbers[i]-numbers[i-window_size]# 更新最小窗口和min_window_sum=min(min_window_sum,current_window_sum)# 猴子能获取的最大香蕉数是总和减去最小窗口和returntotal-min_window_sum# 读取数组长度array_length=int(input())# 读取数组，将输入的字符串分割并转换为整数列表numbers=list(map(int,input().strip().split()))# 读取猴子可以获取的次数N=int(input())# 输出猴子能获取的最大香蕉数print(max_bananas(numbers,N))

Go

packagemainimport("fmt""math")funcmain(){varlenintfmt.Scan(&len)// 读取数组长度numbers:=make([]int,len)// 创建数组存储每串香蕉的数量fori:=0;i<len;i++{fmt.Scan(&numbers[i])// 循环读取每串香蕉的数量}varNintfmt.Scan(&N)// 读取猴子可以获取的次数fmt.Println(maxBananas(numbers,N))// 输出猴子能获取的最大香蕉数}// 定义方法计算猴子能获取的最大香蕉数funcmaxBananas(numbers[]int,Nint)int{total:=0// 初始化数组总和为0// 计算数组中所有香蕉的总数for_,number:=rangenumbers{total+=number}// 如果N等于数组长度，猴子可以拿走所有的香蕉ifN==len(numbers){returntotal}minWindowSum:=math.MaxInt32// 初始化最小窗口和为最大整数值currentWindowSum:=0// 初始化当前窗口和为0windowSize:=len(numbers)-N// 计算窗口大小// 初始化窗口的和fori:=0;i<windowSize;i++{currentWindowSum+=numbers[i]}minWindowSum=currentWindowSum// 将当前窗口和赋值给最小窗口和// 通过滑动窗口计算最小窗口和fori:=windowSize;i<len(numbers);i++{// 窗口滑动，加上新进入窗口的元素，减去离开窗口的元素currentWindowSum+=numbers[i]-numbers[i-windowSize]// 更新最小窗口和minWindowSum=min(minWindowSum,currentWindowSum)}// 猴子能获取的最大香蕉数是总和减去最小窗口和returntotal-minWindowSum}// 辅助函数：返回两个整数中的较小值funcmin(a,bint)int{ifa<b{returna}returnb}

C语言

#include<stdio.h>#include<limits.h>// 计算猴子能获取的最大香蕉数intmaxBananas(intnumbers[],intlen,intN){inttotal=0;// 初始化数组总和为0// 计算数组中所有香蕉的总数for(inti=0;i<len;i++){total+=numbers[i];}// 如果N等于数组长度，猴子可以拿走所有的香蕉if(N==len){returntotal;}intminWindowSum=INT_MAX;// 初始化最小窗口和为最大整数值intcurrentWindowSum=0;// 初始化当前窗口和为0intwindowSize=len-N;// 计算窗口大小// 初始化窗口的和for(inti=0;i<windowSize;i++){currentWindowSum+=numbers[i];}minWindowSum=currentWindowSum;// 将当前窗口和赋值给最小窗口和// 通过滑动窗口计算最小窗口和for(inti=windowSize;i<len;i++){// 窗口滑动，加上新进入窗口的元素，减去离开窗口的元素currentWindowSum+=numbers[i]-numbers[i-windowSize];// 更新最小窗口和if(currentWindowSum<minWindowSum){minWindowSum=currentWindowSum;}}// 猴子能获取的最大香蕉数是总和减去最小窗口和returntotal-minWindowSum;}intmain(){intlen;// 读取数组长度scanf("%d",&len);intnumbers[len];// 创建数组存储每串香蕉的数量for(inti=0;i<len;i++){scanf("%d",&numbers[i]);// 循环读取每串香蕉的数量}intN;// 读取猴子可以获取的次数scanf("%d",&N);printf("%d\n",maxBananas(numbers,len,N));// 输出猴子能获取的最大香蕉数return0;}

完整用例

用例1

5 2 4 5 1 3 2

用例2

6 1 3 2 5 4 2 3

用例3

4 5 1 2 3 2

用例4

8 3 2 7 1 2 6 4 5 4

用例5

10 1 2 3 4 5 6 7 8 9 10 5

用例6

7 10 20 30 40 50 60 70 3

用例7

3 3 2 1 2

用例8

9 1 3 5 7 9 11 13 15 17 5

用例9

6 6 7 8 1 2 3 4

用例10

5 4 1 2 3 4 3