监利县建设局网站,招商信息发布网站大全,东莞找公司网站,新乡seo网络推广费用#xff01;#xff01;#xff01;思路和代码源自蓝桥云课大佬题解 问题描述 小青蛙住在一条河边#xff0c;它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。 河里的石头排成了一条直线小青蛙每次跳跃必须落在一块石头或者岸上。 不过,每块石头有一个高度,…思路和代码源自蓝桥云课大佬题解 问题描述 小青蛙住在一条河边它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。 河里的石头排成了一条直线小青蛙每次跳跃必须落在一块石头或者岸上。 不过,每块石头有一个高度,每次小青蛙从一块石头起跳这块石头的高度就会下降1当石头的高度下降到0时小青蛙不能再跳到这块石头上(某次跳跃后使石头高度下降到0是允许的)。 小青蛙一共需要去学校上 天课,所以它需要往返2次。当小青蛙具有一个跳跃能力y时它能跳不超过的距离。 请问小青蛙的跳跃能力至少是多少才能用这些石头上完a次课。 输入格式 输入的第一行包含两个整数n,a,分别表示河的宽度和小青蛙需要去学校的天数。请注意2才是实际过河的次数。 第二行包含n-1个非负整数 H1, H2,··,Hn-1,其中H0表示在河中与小青蛙的家相距的地方有一块高度为H;的石头H;0表示这个位置没有石头。 输出格式 输出一行包含一个整数,表示小青蛙需要的最低跳跃能力。 样例输入
5 1
1 0 1 0
输出
4 import os
import sys# 请在此输入您的代码n,xmap(int,input().split())
Hlist(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[iy]-sum_H[i]2*x:return Falsereturn True #所有都大于才是正确 # 所有位置都满足条件才返回Truel,r1,n
while(lr):mid(lr)//2if check(mid): #高度大于2x缩减到左半部分求最低跳跃能力rmid-1else:lmid1if check(r):print(r)
else:print(r1)
