CF716A.Crazy Computer
入门
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
ZS the Coder is coding on a crazy computer. If you don't type in a word for a c consecutive seconds, everything you typed disappear!
More formally, if you typed a word at second a and then the next word at second b, then if b - a ≤ c, just the new word is appended to other words on the screen. If b - a > c, then everything on the screen disappears and after that the word you have typed appears on the screen.
For example, if c = 5 and you typed words at seconds 1, 3, 8, 14, 19, 20 then at the second 8 there will be 3 words on the screen. After that, everything disappears at the second 13 because nothing was typed. At the seconds 14 and 19 another two words are typed, and finally, at the second 20, one more word is typed, and a total of 3 words remain on the screen.
You're given the times when ZS the Coder typed the words. Determine how many words remain on the screen after he finished typing everything.
ZS 程序员正在一台“疯狂”的电脑上编程。如果你连续 c 秒没有输入任何单词,那么屏幕上所有已输入的内容都会消失!
更形式化地讲:若你在第 a 秒输入了一个单词,紧接着在第 b 秒输入了下一个单词,则当 b − a ≤ c 时,新输入的单词仅被追加到屏幕上已有的单词之后;而当 b − a > c 时,屏幕上所有内容将全部清空,随后你刚输入的单词单独显示在屏幕上。
例如,若 c = 5,且你在第 1、3、8、14、19、20 秒依次输入了单词,则在第 8 秒时屏幕上将显示 3 个单词。随后,由于第 13 秒时未输入任何内容,屏幕上的所有内容将在该时刻消失。接着,在第 14 秒和第 19 秒又分别输入了两个单词;最后,在第 20 秒再输入一个单词,此时屏幕上共保留 3 个单词。
现给出 ZS 程序员输入各个单词的具体时刻,请确定他完成全部输入后,屏幕上剩余的单词数量。
输入格式
The first line contains two integers n and c (1 ≤ n ≤ 100 000, 1 ≤ c ≤ 109) — the number of words ZS the Coder typed and the crazy computer delay respectively.
The next line contains n integers _t_1, _t_2, ..., t__n (1 ≤ _t_1 < _t_2 < ... < t__n ≤ 109), where t__i denotes the second when ZS the Coder typed the i-th word.
第一行包含两个整数 n 和 c(1 ≤ n ≤ 100000,1 ≤ c ≤ 109)——分别表示 ZS the Coder 输入的单词数量以及“疯狂计算机”的延迟时间。
下一行包含 n 个整数 t1,t2,...,tn(1 ≤ t1 < t2 < ... < tn ≤ 109),其中 ti 表示 ZS the Coder 输入第 i 个单词的时刻(单位:秒)。
输出格式
Print a single positive integer, the number of words that remain on the screen after all n words was typed, in other words, at the second t__n.
输出一个正整数,表示在所有 n 个单词输入完毕后(即第 tn 秒)屏幕上剩余的单词数量。
输入输出样例
输入#1
6 5 1 3 8 14 19 20
输出#1
3
输入#2
6 1 1 3 5 7 9 10
输出#2
2
说明/提示
The first sample is already explained in the problem statement.
For the second sample, after typing the first word at the second 1, it disappears because the next word is typed at the second 3 and 3 - 1 > 1. Similarly, only 1 word will remain at the second 9. Then, a word is typed at the second 10, so there will be two words on the screen, as the old word won't disappear because 10 - 9 ≤ 1.
第一个样例已在题目描述中解释。
对于第二个样例,在第 1 秒输入第一个单词后,该单词会消失,因为下一个单词在第 3 秒被输入,且 3 − 1 > 1。类似地,在第 9 秒时屏幕上仅剩 1 个单词。随后,在第 10 秒输入一个新单词,此时屏幕上将有两个单词,因为旧单词不会消失(满足 10 − 9 ≤ 1)。
输入解题思路,AI测评打分。不知道怎么写?