小青蛙住在一条河边, 它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。 河里的石头排成了一条直线, 小青蛙每次跳跃必须落在一块石头或者岸上。 不过, 每块石头有一个高度, 每次小青蛙从一块石头起跳, 这块石头的高度就会下降 1 , 当石头的高度下降到 0 时小青蛙不能再跳到这块石头上(某次跳跃 后使石头高度下降到 0 是允许的)。 小青蛙一共需要去学校上 x 天课, 所以它需要往返 2 x 次。当小青蛙具有一个跳跃能力 y时, 它能跳不超过 y的距离。 请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x次课。 输入格式 输入的第一行包含两个整数 n , x分别表示河的宽度和小青蛙需要去学校的天数。请注意 2 x才是实际过河的次数。 第二行包含 n − 1个非负整数 H 1 , H 2 , ⋯ , H n − 1 , 其中 H i >0,表示在河中与小青蛙的家相距 i 的地方有一块高度为 H i的石头,H i = 0表示这个位置没有石头。 输出格式 输出一行, 包含一个整数, 表示小青蛙需要的最低跳跃能力。 样例输入 5 1 1 0 1 0 样例输出 4帮我写出c语言代码并给出题目思路
时间: 2023-06-15 14:05:19 浏览: 62
题目思路:
这是一个典型的二分答案问题。我们可以通过二分来确定小青蛙的最低跳跃能力。具体来说,我们可以枚举每一次跳跃的起点和终点,然后判断是否能成功跳到对岸。如果能成功跳到对岸,则继续枚举下一次跳跃,否则需要调整跳跃能力。
判断能否成功跳到对岸,可以使用贪心的思想。我们可以从起点开始,每次选择当前能够跳到的最远的石头作为跳跃终点,然后再以当前终点作为起点,继续选择能够跳到的最远的石头作为下一次跳跃的终点,直到跳到对岸或者无法跳到更远的石头为止。
代码实现:
在代码实现中,我们可以先将石头的高度按照距离从小到大排序,然后每次枚举起点和终点时,只需要考虑当前终点之后的石头即可。这样可以大大减少枚举的次数,提高程序效率。
注意:在判断能否成功跳到对岸时,需要特别注意最后一次跳跃的情况,因为最后一次跳跃不需要落在石头上,而是直接跳到对岸。
代码如下:
相关问题
小青蛙gd32f303库函数
小青蛙GD32F303库函数是一组用于开发基于GD32F303芯片的小青蛙项目的函数集合。它提供了丰富的功能和接口,使得开发者可以轻松地控制和操作芯片的各种功能。
在小青蛙GD32F303库函数中,包含了众多的功能模块,如时钟控制、GPIO控制、中断控制、定时器、ADC、UART和SPI等。通过这些库函数,开发者可以方便地配置和使用这些功能模块,实现小青蛙项目的各种需求。
比如,开发者可以使用库函数来配置和控制GPIO口的输入输出状态,实现与其他外设的连接和通信。通过配置时钟控制模块,开发者可以设置系统时钟频率,以满足不同的应用需求。
而定时器和中断控制模块的库函数,可以帮助开发者实现定时任务和中断处理的功能。通过配置定时器的计数值和中断触发条件,开发者可以实现定时触发某些操作或处理特定的中断事件。
另外,库函数还提供了ADC模块的配置和使用函数,以便开发者能够实现模拟信号的采集和转换。UART和SPI模块的库函数则可以帮助开发者实现与其他设备之间的串行通信和数据交换。
总的来说,小青蛙GD32F303库函数提供了一套简洁、高效的代码接口,使得开发者能够更加方便地进行小青蛙项目的开发和调试工作。无论是控制IO口、配置时钟、处理定时器中断,还是进行模拟信号采集和串行通信,开发者都可以使用库函数来简化开发流程,提高开发效率。
先有 � N 块石头,编号为 1 , 2 , 3 , . . . , � 1,2,3,...,N。每块石头 � ( 1 ≤ � ≤ � ) i(1≤i≤N) 对应的高度为 ℎ � h i 。 最初小青蛙图图站在石头 1 1 上,他将重复若干次以下操作以到达石头 � N: 如果图图当前站在石头 � i 上,则可以跳到石头 � + 1 i+1 或 � + 2 i+2 上。需要 ∣ ℎ � − ℎ � ∣ ∣h i −h j ∣的体力, � ( � ≤ � ) j(j≤n) 是要落到的石头的编号。 请帮小青蛙图图计算出从石头 1 1 跳到石头 � N 上需要的最小体力值。
这是一个典型的动态规划问题,可以使用动态规划来解决。
首先,定义一个数组 dp,其中 dp[i] 表示从石头 1 跳到石头 i 需要的最小体力值。
根据题目的要求,我们可以得到状态转移方程:
dp[i] = min(dp[i-1] + |h[i] - h[i-1]|, dp[i-2] + |h[i] - h[i-2]|)
其中,dp[i-1] 表示从石头 1 跳到石头 i-1 需要的最小体力值,dp[i-2] 表示从石头 1 跳到石头 i-2 需要的最小体力值。
根据状态转移方程,我们可以逐个计算 dp 数组的值。
最终,dp[N] 就是从石头 1 跳到石头 N 需要的最小体力值。
以下是一个示例的实现代码:
```python
def min_energy(N, heights):
dp = [0] * (N+1)
dp[1] = 0
for i in range(2, N+1):
dp[i] = min(dp[i-1] + abs(heights[i] - heights[i-1]), dp[i-2] + abs(heights[i] - heights[i-2]))
return dp[N]
N = int(input("请输入石头的数量:"))
heights = [0] * (N+1)
for i in range(1, N+1):
heights[i] = int(input("请输入石头 {} 的高度:".format(i)))
result = min_energy(N, heights)
print("从石头 1 跳到石头 {} 需要的最小体力值为:{}".format(N, result))
```
你可以根据需要修改输入方式和输出方式,以适应你的实际情况。