分数: 333 分
问题陈述
高桥正在果园做一份摘苹果的兼职工作。果园有 N 苹果,每个位于树上的不同高度。
的 i-第一个苹果的高度为 H_i 距地面厘米。高桥的身高是 T 厘米,但通过伸展脚趾,他可以达到的最大高度 T + K 厘米。
要收获苹果,苹果的高度必须在他够得着的范围内(最多 T + K 厘米)。对于他够不到的苹果,他需要使用活梯。
由于高桥发现使用活梯很麻烦,因此他希望通过单独伸展来最大限度地增加收获的苹果数量。幸运的是,这个果园里的树都是种植在特制的移动花盆里的,他可以挖一个深度的洞 D 厘米在地下沉入整个花盆(D 是任何非负整数)。当一棵树下沉时,它所有苹果的高度都会均匀减少 D.
但是,有一个限制,即最低苹果的高度不得小于 1 厘米。换句话说,对于所有 i,条件 必须满足 H_i - D \geq 1 。
求高桥仅通过拉伸可以收获的最大苹果数量。
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq T \leq 10^9
- 0 \leq K \leq 10^9
- 1 \leq H_i \leq 10^9 (1 \leq i \leq N)
- 所有输入均为整数
输入
N T K H_1 H_2 \ldots H_N
- 第一行包含苹果的数量 N, 高桥的身高 T,以及附加高度 K 他可以通过伸展来到达,之间有空格。
- 第二行包含每个苹果的高度 H_1, H_2, \ldots, H_N,用空格分隔。
输出
在一行中打印 Takahashi 通过单独拉伸可以收获的最大苹果数量。
示例输入 1
5 150 30 100 160 180 200 250
示例输出 1
5
示例输入 2
5 100 10 50 80 120 200 300
示例输出 2
3
示例输入 3
10 200 50 10 30 50 100 150 200 260 300 350 400
示例输出 3
6
示例输入 4
15 500 100 1 50 100 200 300 400 500 550 580 590 600 650 700 800 1000
示例输出 4
11
示例输入 5
1 1 0 1
示例输出 5
1