CF716A.Crazy Computer

传统题 时间 2000 ms 内存 256 MiB 3 尝试 1 已通过 1 标签

Crazy Computer

题目描述

ZS the Coder 正在一台疯狂的计算机上编程。如果你在连续 cc 秒内没有输入任何单词,你输入的所有内容都会消失!

更正式地说,如果你在第 aa 秒输入了一个单词,而下一个单词在第 bb 秒输入,如果 bacb-a \leq c,新输入的单词会被添加到屏幕上的其它单词后面。如果 ba>cb-a > c,那么屏幕上的所有内容都会消失,之后你输入的单词会单独显示在屏幕上。

例如,如果 c=5c=5 并且你分别在 1,3,8,14,19,201,3,8,14,19,20 秒输入了单词,那么在第 88 秒时,屏幕上会有 33 个单词。之后,因为第 1313 秒没有输入单词,所有内容都会消失。在第 1414 秒和第 1919 秒,又输入了两个单词,最后在第 2020 秒再输入一个单词,屏幕上一共保留了 33 个单词。

你已知 ZS the Coder 输入单词的时间。请计算在他完成所有输入后,屏幕上还剩下多少个单词。

输入格式

第一行包含两个整数 nncc1n100000,1c1091 \leq n \leq 100000, 1 \leq c \leq 10^{9}),分别表示 ZS the Coder 输入的单词数和疯狂计算机的延迟时间。

第二行包含 nn 个正整数 t1,t2,,tnt_1, t_2, \ldots, t_n1t1<t2<<tn1091 \leq t_1 < t_2 < \ldots < t_n \leq 10^{9}),其中 tit_i 表示 ZS the Coder 输入第 ii 个单词的时间(以秒为单位)。

输出格式

输出一个正整数,表示当所有 nn 个单词输入完毕后(即在第 tnt_n 秒时),屏幕上剩余的单词数。

说明/提示

第一个样例已在题目描述中给出了解释。

对于第二个样例,第一在第 11 秒输入一个单词,内容随后消失,因为下一个单词在第 33 秒输入,且 31>13-1>1。同理,在第 99 秒时也只剩下 11 个单词。之后在第 1010 秒再输入一个单词,因此此时屏幕上会有两个单词,因为旧单词没有消失,满足 109110-9\leq 1

由 ChatGPT 5 翻译

样例

6 5
1 3 8 14 19 20
3
6 1
1 3 5 7 9 10
2

在线编程 IDE

建议全屏模式获得最佳体验