J. [蓝桥杯 2024 国 B] 立定跳远

Type: RemoteJudge

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

在运动会上，小明从数轴的原点开始向正方向立定跳远。项目设置了 $n$ 个检查点 $a_1, a_2, \cdots , a_n$ 且 $a_i \ge a_{i−1} > 0$ 。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时，小明可以自行再增加 $m$ 个检查点让自己跳得更轻松。

在运动会前，小明制定训练计划让自己单次跳跃的最远距离达到 $L$ ，并且学会一个爆发技能可以在运动会时使用一次，使用时可以在该次跳跃时的最远距离变为 $2L$ 。小明想知道， $L$ 的最小值是多少可以完成这个项目？

输入共 $2$ 行。

第一行为两个正整数 $n,m$ 。

第二行为 $n$ 个由空格分开的正整数 $a_1, a_2, \cdots, a_n$ 。

输出共 $1$ 行，一个整数表示答案。

5 3
1 3 5 16 21

【样例说明】

增加检查点 $10, 13, 19$ ，因此每次跳跃距离为 $1,2, 2, 5, 3, 3, 3, 2$ ，在第三次跳跃时使用技能即可。

【评测用例规模与约定】

对于 $20\%$ 的评测用例，保证 $n \le 10^2$ ， $m \le 10^3$ ， $a_i \le 10^3$ 。
对于 $100\%$ 的评测用例，保证 $2 \le n \le 10^5$ ， $m \le 10^8$ ， $0 < a_i \le 10^8$ 。