噜噜的羊圈
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
噜噜的羊圈
题目背景
小羊们活泼可爱,噜噜决定为它们建造一个舒适的羊圈。羊圈由许多分布在一条直线上的木桩支撑,然后用木板连接相邻的木桩形成围栏。
最近,一只特别小的羊宝宝诞生了,噜噜担心它会从某些木桩间隙中钻出去。噜噜测量了所有木桩的位置,并知道小羊宝宝能钻过的最大缝隙宽度。现在,他想请你帮忙统计一下,有多少段相邻木桩之间的间隙,宽度是小于或等于小羊宝宝能钻过的最大宽度的。
问题描述
给定数轴上 N
个木桩的位置,以及小羊宝宝能钻过的最大缝隙宽度 K
。你需要计算,在所有由相邻木桩形成的间隙中,有多少个间隙的宽度小于或等于 K
。
注意:木桩的位置可能是乱序给出的,你需要先确定哪些木桩是相邻的。在数轴上,A点和B点相邻,当且仅当不存在第三个木桩C的位置在A和B之间。
输入格式
第一行包含两个正整数 N
和 K
,分别表示木桩的数量和小羊宝宝能钻过的最大缝隙宽度。
第二行包含 N
个整数 P_1, P_2, ..., P_N
,表示每个木桩在数轴上的位置。
输出格式
输出一个整数,表示宽度小于或等于 K
的相邻木桩间隙的数量。
样例输入与输出
样例输入 #1
5 3
1 10 4 15 7
样例输出 #1
3
样例解释 #1 木桩的位置是 1, 10, 4, 15, 7。 将它们排序后得到:1, 4, 7, 10, 15。 相邻木桩及间隙宽度为:
- (1, 4):间隙宽度 4 - 1 = 3。3 <= 3 (K),计数。
- (4, 7):间隙宽度 7 - 4 = 3。3 <= 3 (K),计数。
- (7, 10):间隙宽度 10 - 7 = 3。3 <= 3 (K),计数。
- (10, 15):间隙宽度 15 - 10 = 5。5 > 3 (K),不计数。 总共有 3 个间隙的宽度小于或等于 3。
样例输入 #2
3 10
20 5 30
样例输出 #2
1
样例解释 #2 木桩的位置是 20, 5, 30。 排序后:5, 20, 30。 样例解释 #2: 木桩的位置是 20, 5, 30。 排序后:5, 20, 30。 相邻木桩及间隙宽度为:
- (5, 20):间隙宽度 20 - 5 = 15。15 > 10 (K),不计数。
- (20, 30):间隙宽度 30 - 20 = 10。10 <= 10 (K),计数。 总共有 1 个间隙的宽度小于或等于 10。因此输出应为1。
样例输入 #2
3 10
20 5 30
样例输出 #2
1
数据范围与约定
对于所有测试数据,保证:
2 <= N <= 10^5
1 <= K <= 10^9
1 <= P_i <= 10^9
- 保证所有
P_i
互不相同。
子任务:
子任务编号 | 特殊限制 | 分值比例 |
---|---|---|
1 | N <= 10 |
20% |
2 | N <= 1000 |
30% |
3 | 无特殊限制 | 50% |