B. 噜噜的羊圈

    传统题 1000ms 256MiB

噜噜的羊圈

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

噜噜的羊圈

题目背景

小羊们活泼可爱,噜噜决定为它们建造一个舒适的羊圈。羊圈由许多分布在一条直线上的木桩支撑,然后用木板连接相邻的木桩形成围栏。

最近,一只特别小的羊宝宝诞生了,噜噜担心它会从某些木桩间隙中钻出去。噜噜测量了所有木桩的位置,并知道小羊宝宝能钻过的最大缝隙宽度。现在,他想请你帮忙统计一下,有多少段相邻木桩之间的间隙,宽度是小于或等于小羊宝宝能钻过的最大宽度的。

问题描述

给定数轴上 N 个木桩的位置,以及小羊宝宝能钻过的最大缝隙宽度 K。你需要计算,在所有由相邻木桩形成的间隙中,有多少个间隙的宽度小于或等于 K

注意:木桩的位置可能是乱序给出的,你需要先确定哪些木桩是相邻的。在数轴上,A点和B点相邻,当且仅当不存在第三个木桩C的位置在A和B之间。

输入格式

第一行包含两个正整数 NK,分别表示木桩的数量和小羊宝宝能钻过的最大缝隙宽度。 第二行包含 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%

「果壳语法杯」ROUND #3 (Div.5)

未参加
状态
已结束
规则
IOI
题目
5
开始于
2025-5-16 19:00
结束于
2025-5-18 21:00
持续时间
2 小时
主持人
参赛人数
62