P3083青蛙表演 | ||
|
问题描述
何老板训练了一只青蛙,该蛙擅长跳跃。它经常从一片荷叶跳到另一片荷叶。今天,何老板打算用N根木桩来向世人展示该蛙的跳跃技能。
这n根木桩排成一行,蛙首先从最矮的木桩顶部起跳,总共进行N-1次跳跃。每次它只能跳到比当前木桩更高的一个木桩顶部。当表演结束时,每个木桩它都恰好到过一次,最终停在最高的木桩顶部。
这只青蛙向上跳跃能力很强,但水平方向跳跃能力就有限了,每次跳跃,它在水平方向飞行的距离不超过D米。舞台上给出的这N根木桩的排列顺序不可改变,但木桩间的间距可以任意调整,但间距必须是整数而且至少为1,且两根木桩不能位于同一点上。何老板想知道,在成功完成表演的前提下,最矮跟最高的那根木桩的间距最大可能是多少?如果无论如何都不能完成表演,输出-1
输入格式
第一行,两个空格间隔的整数N和D
第二行,N个空格间隔的整数,依次给出了每根木桩的高度,不会有相同高度的木桩,木桩的高度在int范围以内。
输出格式
一个整数,表示最矮和最高木桩可能的最大间距
若不可能完成表演,输出-1
样例输入 1
样例1:
4 4
20 30 10 40
样例2:
4 2
10 20 16 13
样例输出 1
样例1:
3
样例2:
-1
样例输入 2
5 6
11 2 24 27 42
样例输出 2
17
提示
【样例解释】
样例1说明:
高度20和高度30的木桩的间距可以是1到3之间的任意数字
高度30和高度10的木桩的间距为1
高度10和高度40的木桩的间距为3
跳跃的顺序是:
1.从10跳到20,间距<=4
2.从20跳到30,间距<=4
3.从30跳到40,间距恰好为4。
【数据范围】
对于40%的数据 1 ≤ N ≤ 100
对于100%的数据 1 ≤ N ≤ 1000 ,1 ≤ D ≤1000000