刷题刷出新高度,偷偷领先!偷偷领先!偷偷领先! 关注我们,悄悄成为最优秀的自己!

简答题

公园树木

题目描述:

某公园有N(3≤N≤50)棵树排成一排,已知每棵树的高度。现要去掉一些树,使得剩下树的高度从左至右呈现先递增再递减的规律(即剩余的树中仅有一棵最高的树,且它左侧的所有树中后一棵树都要比前一棵树高,它右侧的所有树中后一棵树都要比前一棵树矮)

给出N棵树的高度(高度单位:m,1.0≤每棵树高度≤100.0,保留一位小数),请你计算出最少去掉几棵树才能使这排树呈现先递增再递减的规律,如果不能呈现则输出-1(只有递增或者只有递减都为不能呈现)。

例如:N=10,10棵树的高度从左到右依次为1.0、2.3、1.2、1.7、1.1、2.0、1.8、1.8、1.2、1.9。

要使这排树呈现先递增再递减的规律,最少去掉4棵树,去掉的编号分别为2、5、8、10。

剩余树的高度依次为1.0、1.2、1.7、2.0、1.8、1.2,最高树为2.0,其左侧树的高度依次为1.0、1.2、1.7、2.0,呈现递增趋势(从左至右且包含最高树);其右侧树的高度依次为2.0、1.8、1.2,呈现递减趋势(从左至右且包含最高树)。

输入描述:

第一行输入一个正整数N(3≤N≤50),表示这排树的数量

第二行输入N个数(1.0≤每个数≤100.0,保留一位小数),表示每棵树的高度,每个数之间以一个空格隔开

输出描述:

输出一个整数,表示最少去掉几棵树才能使这排树呈现先递增再递减的规律,如果不能呈现则输出-1


样例输入:

10
1.0 2.3 1.2 1.7 1.1 2.0 1.8 1.8 1.2 1.9

样例输出:

4

使用微信搜索喵呜刷题,轻松应对考试!

答案:

对于给定的树的高度序列,我们需要找到最少去掉的树的数量,使得剩下的树的高度从左至右呈现先递增再递减的规律。首先,我们需要找到最高的树,并确定它的位置。然后,我们需要检查最高树左侧和右侧的树是否满足递增和递减的规律。如果最高树左侧的所有树中后一棵树都要比前一棵树高,且最高树右侧的所有树中后一棵树都要比前一棵树矮,那么我们就可以确定剩下的树呈现先递增再递减的规律。如果最高树左侧或右侧的树不满足递增或递减的规律,那么我们就需要去掉一些树,使得剩下的树满足规律。为了找到最少去掉的树的数量,我们可以从最高树开始,向两侧扩展,找到需要去掉的树。具体步骤如下:1. 找到最高的树,并记录它的位置。2. 检查最高树左侧和右侧的树是否满足递增和递减的规律。3. 如果满足规律,直接输出0,表示不需要去掉任何树。4. 如果不满足规律,从最高树开始,向两侧扩展,找到需要去掉的树,并计算去掉的树的数量。对于样例输入,最高树的位置是6,它的左侧和右侧的树不满足递增和递减的规律,需要去掉一些树。从最高树开始,向左侧扩展,需要去掉的树的位置是2、5、8、10,一共需要去掉4棵树。因此,最少去掉4棵树才能使这排树呈现先递增再递减的规律。

解析:

【喵呜刷题小喵解析】:

这个问题是一个典型的贪心算法问题。首先,我们需要找到最高的树,然后分别向左右两侧扩展,检查是否满足递增和递减的规律。如果不满足,就需要去掉一些树,使得剩下的树满足规律。

为了找到最少去掉的树的数量,我们可以从最高树开始,向两侧扩展,找到需要去掉的树。具体步骤如下:

1. 找到最高的树,并记录它的位置。
2. 从最高树开始,向左侧扩展,找到第一个不满足递增规律的树,去掉这个树及其后面的所有树。
3. 从最高树开始,向右侧扩展,找到第一个不满足递减规律的树,去掉这个树及其前面的所有树。
4. 返回去掉的树的数量。

这种方法可以保证去掉的树的数量最少,因为我们在去掉树的同时,尽量保留更多的树,使得剩下的树尽可能满足规律。

需要注意的是,如果最高树左侧或右侧的树不满足递增或递减的规律,我们需要分别向左右两侧扩展,找到需要去掉的树。如果最高树左侧和右侧的树都满足规律,那么就不需要去掉任何树,直接输出0即可。

对于样例输入,最高树的位置是6,它的左侧和右侧的树不满足递增和递减的规律,需要去掉一些树。从最高树开始,向左侧扩展,需要去掉的树的位置是2、5、8、10,一共需要去掉4棵树。因此,最少去掉4棵树才能使这排树呈现先递增再递减的规律。
创作类型:
原创

本文链接:公园树木 题目描述: 某公园有N(3≤N≤50)棵树排成一排,已知每棵树的高度。现要去掉一些树,使得

版权声明:本站点所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速,微信扫码,获取考试解析、体验刷题服务,开启你的学习加速器!

分享考题
share