青蛙过河。

本文主要是介绍青蛙过河。，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

！！！思路和代码源自蓝桥云课大佬题解
问题描述
小青蛙住在一条河边，它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。
河里的石头排成了一条直线小青蛙每次跳跃必须落在一块石头或者岸上。 不过,每块石头有一个高度,每次小青蛙从一块石头起跳，这块石头的高度就会下降1当石头的高度下降到0时小青蛙不能再跳到这块石头上(某次跳跃后使石头高度下降到0是允许的)。
小青蛙一共需要去学校上 天课,所以它需要往返2次。当小青蛙具有一个跳跃能力y时它能跳不超过的距离。
请问小青蛙的跳跃能力至少是多少才能用这些石头上完a次课。
输入格式
输入的第一行包含两个整数n,a,分别表示河的宽度和小青蛙需要去学校的天数。请注意2才是实际过河的次数。
第二行包含n-1个非负整数 H1, H2,··,Hn-1,其中H，>0表示在河中与小青蛙的家相距的地方有一块高度为H;的石头，H;0表示这个位置没有石头。
输出格式
输出一行，包含一个整数,表示小青蛙需要的最低跳跃能力。
样例输入

5 1

1 0 1 0

输出

4

import os
import sys# 请在此输入您的代码n,x=map(int,input().split())
H=list(map(int,input().split())) #n-1个
sum_H=[0]*n
for i in range(1,n):sum_H[i]=sum_H[i-1]+H[i-1]   #从sum_H[1]到sum_H[n-1],总共n-2个def check(y):for i in range(n-y):  #最后一跳站在n-y的位置上if sum_H[i+y]-sum_H[i]<2*x:return Falsereturn True  #所有都大于才是正确， # 所有位置都满足条件才返回Truel,r=1,n
while(l<=r):mid=(l+r)//2if check(mid):  #高度大于2x，缩减到左半部分（求最低跳跃能力）r=mid-1else:l=mid+1if check(r):print(r)
else:print(r+1)

这篇关于青蛙过河。的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---