AT_abc480_c.Self-Stopping Shower
普及-
通过率:0%
时间限制:2.00s
内存限制:1024MB
AC君温馨提醒
该题目为【atcoder】题库的题目,您提交的代码将被提交至atcoder进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Takahashi is using a shower at a public bath. This shower has a button. If the button is pressed at time t, hot water comes out for K seconds, from time t to time t+K. Even if the button is pressed again while hot water is coming out, hot water comes out for K seconds from the time the button was last pressed.
There are N Aokis, each of whom presses the button once. The i-th Aoki presses the button at time Ai.
Find the minimum number of times Takahashi needs to press the button so that hot water is always coming out from time 0 to time T. Here, hot water is considered to be coming out both at the moment the button is pressed and at the moment exactly K seconds after the last press.
高桥正在公共浴场使用淋浴。该淋浴有一个按钮。若在时刻 t 按下按钮,则从时刻 t 到时刻 t+K(含端点)会持续流出热水,共 K 秒。即使在热水正在流出期间再次按下按钮,热水也仅会从最后一次按下按钮的时刻起持续流出 K 秒。
共有 N 个青木,每人恰好按下按钮一次。第 i 个青木在时刻 Ai 按下按钮。
求高桥为确保从时刻 0 到时刻 T(含端点)始终有热水流出,所需按动按钮的最少次数。注意:在按钮被按下的瞬间,以及在最后一次按下按钮后恰好 K 秒的时刻,均视为有热水流出。
输入格式
The input is given from Standard Input in the following format:
N K T
A1 A2 … AN
输入从标准输入中按以下格式给出:
N K T
A1 A2 … AN
输出格式
Print the answer in a single line.
在一行中输出答案。
输入输出样例
输入#1
3 4 20 6 7 12
输出#1
4
输入#2
9 37 480 12 123 132 213 231 312 321 500 1000
输出#2
11
说明/提示
Sample 1 Explanation:
If Takahashi presses the button at times 0,2,10,16, hot water is always coming out from time 0 to time 20.
If he presses the button 3 times or fewer, it is impossible to keep hot water always coming out, so the answer is 4.
Constraints
- 1≤N≤2×105
- 1≤K≤109
- 1≤T≤109
- 0≤Ai≤109
- All input values are integers.
样例 1 解释:
如果高桥在时刻 0,2,10,16 按下按钮,则从时刻 0 到时刻 20 热水将始终流出。
如果按下按钮的次数不超过 3 次,则无法保证热水始终流出,因此答案为 4。
限制条件
- 1≤N≤2×105
- 1≤K≤109
- 1≤T≤109
- 0≤Ai≤109
- 所有输入值均为整数。
输入解题思路,AI测评打分。不知道怎么写?