1976. 【蓝桥杯省赛2022C++A组民间数据】F: 青蛙过河

时间限制 1000 ms   内存限制 256 MB

小青蛙住在一条河边,它想到河对岸的学校去学习。小青蛙打算经过河里的石头跳到对岸。 河里的石头排成了一条直线,小青蛙每次跳跃必须落在一块石头或者岸上。 不过,每块石头有一个高度,每次小青蛙从一块石头起跳,这块石头的高度就会下降 1,当石头的高度下降到 0 时小青蛙不能再跳到这块石头上(某次跳跃后使石头高度下降到 0 是允许的)。 小青蛙一共需要去学校上 x 天课,所以它需要往返 2x 次。当小青蛙具有一个跳跃能力 y 时,它能跳不超过 y 的距离。 请问小青蛙的跳跃能力至少是多少才能用这些石头上完 x 次课。

输入数据

XBi3J.png
XBrBF.png

注:$H_i$ 范围修改为 $0 \le H_i \le 10^4$

输出数据

输出一行,包含一个整数,表示小青蛙需要的最低跳跃能力。

样例输入

复制
5 1
1 0 1 0 · \n
 · · · \n

样例输出

复制
4 \n

样例说明

由于只有两块高度为 1 的石头,所以往返只能各用一块。第 1 块石头和对岸的距离为 4,如果小青蛙的跳跃能力为 3 则无法满足要求。所以小青蛙最少需要 4 的跳跃能力。

提交

请先 登录

© 2024 FAQs Contact About