分数: 433 分
问题陈述
高桥正计划在山区徒步旅行。
本课程包括 N 沿直线排列的点,以及点的高程 i (1 \leq i \leq N)是 H_i。高桥从点开始 1 并走到指定地点 N 通过点进行 1, 2, \ldots, N 按顺序。
高桥有恐高症,当从某个点移动时 i 来点 i+1 (1 \leq i \leq N-1),如果海拔降低了 K 或更多(也就是说,如果 H_i - H_{i+1} \geq K)。在任何其他动作中他都不会感到恐惧。
课程管理员可以选择任意数字(可能是 0) 来自点的点 2, 3, \ldots, N-1 并将它们的每个高度更改为任何非负整数值,以便高桥可以行走而不会感到恐惧。不同的点可以更改为不同的值,并且更改的值没有上限。然而,点的高程 1 和 N 无法更改。
找到需要更改高程的最少点数,以便高桥可以从该点步行 1 来点 N 从未感到恐惧。如果无论高程如何改变都无法避免恐惧,则输出 -1.
注意: 即使当 N \geq 3,答案可能是 -1。如果不变点之间的高程差 1 和 N 太大,无论中间点的高程如何改变,都无法避免恐惧。
约束
- 2 \leq N \leq 3 \times 10^5
- 1 \leq K \leq 10^9
- 0 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N K H_1 H_2 \ldots H_N
第一行包含点数 N 和海拔下降阈值 K 触发恐惧,以空格分隔。第二行包含每个点的高程 H_1, H_2, \ldots, H_N,用空格分隔。
输出
在一行中打印需要更改高程的最少点数,以便高桥可以从该点步行 1 来点 N 从未感到恐惧。如果无法避免恐惧,就输出 -1.
示例输入 1
5 3 10 8 4 5 3
示例输出 1
1
示例输入 2
3 5 20 0 5
示例输出 2
-1
示例输入 3
12 4 15 13 9 12 8 6 10 5 4 7 3 2
示例输出 3
4
示例输入 4
30 7 100 95 90 82 85 78 70 72 65 60 54 58 50 49 42 35 38 31 25 20 23 18 12 10 5 8 3 2 1 0
示例输出 4
8
示例输入 5
2 1 0 0
示例输出 5
0