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 tt, hot water comes out for KK seconds, from time tt to time t+Kt+K. Even if the button is pressed again while hot water is coming out, hot water comes out for KK seconds from the time the button was last pressed.

There are NN Aokis, each of whom presses the button once. The ii-th Aoki presses the button at time AiA_i.

Find the minimum number of times Takahashi needs to press the button so that hot water is always coming out from time 00 to time TT. Here, hot water is considered to be coming out both at the moment the button is pressed and at the moment exactly KK seconds after the last press.

高桥正在公共浴场使用淋浴。该淋浴有一个按钮。若在时刻 tt 按下按钮,则从时刻 tt 到时刻 t+Kt+K(含端点)会持续流出热水,共 KK 秒。即使在热水正在流出期间再次按下按钮,热水也仅会从最后一次按下按钮的时刻起持续流出 KK 秒。

共有 NN 个青木,每人恰好按下按钮一次。第 ii 个青木在时刻 AiA_i 按下按钮。

求高桥为确保从时刻 00 到时刻 TT(含端点)始终有热水流出,所需按动按钮的最少次数。注意:在按钮被按下的瞬间,以及在最后一次按下按钮后恰好 KK 秒的时刻,均视为有热水流出。

输入格式

The input is given from Standard Input in the following format:

NN KK TT
A1A_1 A2A_2 …\ldots ANA_N

输入从标准输入中按以下格式给出:

NN KK TT
A1A_1 A2A_2 …\ldots ANA_N

输出格式

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,160,2,10,16, hot water is always coming out from time 00 to time 2020.
If he presses the button 33 times or fewer, it is impossible to keep hot water always coming out, so the answer is 44.

Constraints

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤K≤1091 \leq K \leq 10^9
  • 1≤T≤1091 \leq T \leq 10^9
  • 0≤Ai≤1090 \leq A_i \leq 10^9
  • All input values are integers.

样例 1 解释:
如果高桥在时刻 0,2,10,160,2,10,16 按下按钮,则从时刻 00 到时刻 2020 热水将始终流出。
如果按下按钮的次数不超过 33 次,则无法保证热水始终流出,因此答案为 44。

限制条件

  • 1≤N≤2×1051 \leq N \leq 2 \times 10^5
  • 1≤K≤1091 \leq K \leq 10^9
  • 1≤T≤1091 \leq T \leq 10^9
  • 0≤Ai≤1090 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入解题思路,AI测评打分。不知道怎么写?

首页