最少需要准备多少香蕉,能保证所有猴子都能吃饱

2023-10-08 11:40

本文主要是介绍最少需要准备多少香蕉,能保证所有猴子都能吃饱,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目描述

动物园有猴山,每天需要给猴子们发香蕉,猴子会排队依次取食。猴子们铺张浪费,会多拿食物,但最多不会拿超过自身食量的二倍且不会超过当前还存在的香蕉的一半,最后—个猴子除外(即最后—个猴子可以拿完剩余的所有香蕉)。
最少需要准备多少香蕉,能保证所有猴子都能吃饱?

解题思路

先考虑只有一个猴子的情况,那么最少需要的香蕉数量即为这个猴子的食量

如果有3个猴子,那么先让第一个猴子拿香蕉,假设它的食量为4,它最多可能拿8个香蕉,最少可能拿4个香蕉,因为题目是要求最少需要准备多少香蕉,我们假设这个猴子知足常乐,只拿了4个香蕉,但是又有要求猴子拿的香蕉不会超过当前还存在的香蕉的一半,那么我们就给它准备8个香蕉,它只拿 了4个,还剩下4个

接下来喂第二个猴子,如果它的食量为3,那么它只拿3个就能吃饱了,但是拿了3个之后就只剩下1个香蕉了,不满足猴子拿的香蕉不会超过当前还存在的香蕉的一半,那么我们在喂第2个猴子的时候就再加入2个香蕉就可以了,假设它也知足常乐,现在一共剩6个香蕉,它拿了3个,还剩下3个香蕉

接下来喂第三个猴子,如果它的食量为3或者,那么它只拿3个就能吃饱了,就不用再加香蕉了
那么喂第一个猴子准备了8个香蕉,喂第二个猴子准备了2个香蕉,喂第三个猴子准备了0个香蕉.最少需要准备的香蕉数量为 8+2+0=10

输入:[4,3,3]
输出:10

现在假设第3个猴子的食量为5,但是现在只剩下3个香蕉了,我们再加2个香蕉就可以让它吃饱了
那么喂第一个猴子准备了8个香蕉,喂第二个猴子准备了2个香蕉,喂第三个猴子准备了2个香蕉.最少需要准备的香蕉数量为 8+2+2=12

输入:[4,3,5]
输出:12

总结:我们一个一个地喂猴子,把每一次需要加入的香蕉数量用一个数组存起来,最后把数组元素相加就可以了,同时我们需要用另一个数组记录每一次喂完之后剩余的香蕉数(节约空间,也可以用变量), 当当前猴子的2倍食量小于等于当前剩余的香蕉数时,需要加入的香蕉数量为0,当当前猴子的2倍食量大于当前剩余的香蕉数时,需要加入的香蕉数量为2倍食量减当前剩余的香蕉数量

动态方程式

for (int i = 1; i < arr.length - 1; i++) {if (2*arr[i] <= dp_remain[i-1]) {dp[i] = 0;dp_remain[i]=dp_remain[i-1]-arr[i];} else {dp[i] = 2 * arr[i] - dp_remain[i-1];dp_remain[i]=dp_remain[i-1]+dp[i]-arr[i];}}

在这里插入图片描述在这里插入图片描述在这里插入图片描述
在这里插入图片描述在这里插入图片描述在这里插入图片描述在这里插入图片描述

代码实现

/*** Created by 此生辽阔 on 2021/3/21 10:50*/
public class Monkey {public static void main(String[] args) {// int []arr={3,5,4,2};int []arr={5,4,6,2,3,1,9};solutionMokey solutionMokey = new solutionMokey();System.out.println(solutionMokey.minBanana(arr));}}
class solutionMokey{int minBanana(int arr[]) {int[] dp = new int[arr.length];//每一次需要加入的香蕉数量int [] dp_remain=new int[arr.length];//每一次喂完剩余的香蕉数量if(arr.length==1)//考虑只有一个猴子的情况{return arr[0];}dp[0] = 2 * arr[0];//当有多个猴子,初始化dpdp_remain[0]=arr[0];//当有多个猴子,初始化 dp_remainfor (int i = 1; i < arr.length - 1; i++) {//计算第2个到第n-1个猴子的投喂情况if (2*arr[i] <= dp_remain[i-1]) {dp[i] = 0;dp_remain[i]=dp_remain[i-1]-arr[i];} else {dp[i] = 2 * arr[i] - dp_remain[i-1];dp_remain[i]=dp_remain[i-1]+dp[i]-arr[i];}}if(arr.length-1>=0&&arr.length-2>=0)//考虑数组越界{if(arr[arr.length-1]>dp_remain[arr.length-2])//计算最后一个猴子的投喂情况{dp[arr.length-1]=arr[arr.length-1]-dp_remain[arr.length-2];}else{dp[arr.length-1]=0;}}int sum=0;for(int j=0;j<=dp.length-1;j++)//dp数组求和,计算最少需要投喂的香蕉数量{System.out.print(dp[j]+" ");sum=sum+dp[j];}System.out.println();return sum;}

结果展示

在这里插入图片描述

代码实现2

为了结约空间,每一次需要加入的香蕉数量和每一次喂完剩余的香蕉数量都可以用变量来表示,同时用sum来记录香蕉总数

package nowcoder;/*** Created by 此生辽阔 on 2021/3/21 10:50*/
public class Monkey {public static void main(String[] args) {// int []arr={3,5,4,2};int []arr={5,4,6,2,3,1,9};solutionMokey solutionMokey = new solutionMokey();System.out.println(solutionMokey.minBanana(arr));}}
class solutionMokey{int minBanana(int arr[]) {int dp = 0;//每一次需要加入的香蕉数量int  dp_remain=0;//每一次喂完剩余的香蕉数量int sum=0;//香蕉总数if(arr.length==1)//考虑只有一个猴子的情况{return arr[0];}dp = 2 * arr[0];//当有多个猴子,初始化dpsum=sum+dp;// dp_remain[0]=arr[0];//当有多个猴子,初始化 dp_remaindp_remain=arr[0];for (int i = 1; i < arr.length - 1; i++) {//计算第2个到第n-1个猴子的投喂情况if (2*arr[i] <= dp_remain) {dp = 0;dp_remain=dp_remain-arr[i];} else {dp = 2 * arr[i] - dp_remain;dp_remain=dp_remain+dp-arr[i];}sum=sum+dp;}if(arr.length-1>=0&&arr.length-2>=0)//考虑数组越界{if(arr[arr.length-1]>dp_remain)//计算最后一个猴子的投喂情况{dp=arr[arr.length-1]-dp_remain;}else{dp=0;}sum=sum+dp;}return sum;}
}

结果展示

在这里插入图片描述

声明:仅代表我个人的解题思路,我只有题目,没有解题方法和标准答案,不知道我的思路是否正确,本文仅供参考,欢迎在评论区留言交流

这篇关于最少需要准备多少香蕉,能保证所有猴子都能吃饱的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/165016

相关文章

Java8需要知道的4个函数式接口简单教程

《Java8需要知道的4个函数式接口简单教程》:本文主要介绍Java8中引入的函数式接口,包括Consumer、Supplier、Predicate和Function,以及它们的用法和特点,文中... 目录什么是函数是接口?Consumer接口定义核心特点注意事项常见用法1.基本用法2.结合andThen链

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中<trim>元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中,<trim>元素用于动态地添加SQL语句的一部分,例如SET或W

C#实现获得某个枚举的所有名称

《C#实现获得某个枚举的所有名称》这篇文章主要为大家详细介绍了C#如何实现获得某个枚举的所有名称,文中的示例代码讲解详细,具有一定的借鉴价值,有需要的小伙伴可以参考一下... C#中获得某个枚举的所有名称using System;using System.Collections.Generic;usi

通过C#获取PDF中指定文本或所有文本的字体信息

《通过C#获取PDF中指定文本或所有文本的字体信息》在设计和出版行业中,字体的选择和使用对最终作品的质量有着重要影响,然而,有时我们可能会遇到包含未知字体的PDF文件,这使得我们无法准确地复制或修改文... 目录引言C# 获取PDF中指定文本的字体信息C# 获取PDF文档中用到的所有字体信息引言在设计和出

关于数据埋点,你需要了解这些基本知识

产品汪每天都在和数据打交道,你知道数据来自哪里吗? 移动app端内的用户行为数据大多来自埋点,了解一些埋点知识,能和数据分析师、技术侃大山,参与到前期的数据采集,更重要是让最终的埋点数据能为我所用,否则可怜巴巴等上几个月是常有的事。   埋点类型 根据埋点方式,可以区分为: 手动埋点半自动埋点全自动埋点 秉承“任何事物都有两面性”的道理:自动程度高的,能解决通用统计,便于统一化管理,但个性化定

业务中14个需要进行A/B测试的时刻[信息图]

在本指南中,我们将全面了解有关 A/B测试 的所有内容。 我们将介绍不同类型的A/B测试,如何有效地规划和启动测试,如何评估测试是否成功,您应该关注哪些指标,多年来我们发现的常见错误等等。 什么是A/B测试? A/B测试(有时称为“分割测试”)是一种实验类型,其中您创建两种或多种内容变体——如登录页面、电子邮件或广告——并将它们显示给不同的受众群体,以查看哪一种效果最好。 本质上,A/B测

Detectorn2预训练模型复现:数据准备、训练命令、日志分析与输出目录

Detectorn2预训练模型复现:数据准备、训练命令、日志分析与输出目录 在深度学习项目中,目标检测是一项重要的任务。本文将详细介绍如何使用Detectron2进行目标检测模型的复现训练,涵盖训练数据准备、训练命令、训练日志分析、训练指标以及训练输出目录的各个文件及其作用。特别地,我们将演示在训练过程中出现中断后,如何使用 resume 功能继续训练,并将我们复现的模型与Model Zoo中的

如何保证android程序进程不到万不得已的情况下,不会被结束

最近,做一个调用系统自带相机的那么一个功能,遇到的坑,在此记录一下。 设备:红米note4 问题起因 因为自定义的相机,很难满足客户的所有需要,比如:自拍杆的支持,优化方面等等。这些方面自定义的相机都不比系统自带的好,因为有些系统都是商家定制的,难免会出现一个奇葩的问题。比如:你在这款手机上运行,无任何问题,然而你换一款手机后,问题就出现了。 比如:小米的红米系列,你启用系统自带拍照功能后

Collection的所有的方法演示

import java.util.ArrayList;import java.util.Collection;import java.util.Iterator;public class TestCollection {/*** @param args* Collection的所有的方法演示* 此程序没有使用泛型,所以可以添加任意类型* 以后如果写到泛型会补充这一方面的内容*/public s