4153: 完全覆盖桥所需的最少防水布数量

内存限制：1024 MB 时间限制：2.000 S
评测方式：文本比较 命题人：
提交：1 解决：1

题目描述

# Bridge and Sheets ## 题目描述 小高买了一座长度为 $L$ 的桥。他决定用长度为 $W$ 的蓝色防水布覆盖这座桥。 在下面，桥上的位置用距离桥左端的距离来表示。当一块防水布的左端放置在位置 $x$（$0 ≤ x ≤ L-W$，$x$ 为实数）时，它覆盖的范围是$[x, x+W]$。（注意两端都包括在内。）他已经放置了 $N$ 块防水布。第 $i$ 块防水布的左端在位置 $a_i$。 至少还需要多少块防水布才能完全覆盖这座桥？这里，当桥上任意一个在 $0$ 和 $L$ 之间（包括 $0$ 和 $L$）的实数位置 $x$ 都被某块防水布覆盖时，我们说桥被完全覆盖了。

输入

## 输入格式 输入从标准输入中给出，格式如下： $N$ $L$ $W$ $a_1$ $\cdots$ $a_N$

输出

## 输出格式 输出完全覆盖桥所需的最少防水布数量。

样例输入 复制 

2 10 3
3 5

样例输出 复制 

2

提示

## 输入输出样例 ### 输入样例1 ``` 2 10 3 3 5 ``` ### 输出样例1 ``` 2 ``` ### 输入样例2 ``` 5 10 3 0 1 4 6 7 ``` ### 输出样例2 ``` 0 ``` ### 输入样例3 ``` 12 1000000000 5 18501490 45193578 51176297 126259763 132941437 180230259 401450156 585843095 614520250 622477699 657221699 896711402 ``` ### 输出样例3 ``` 199999992 ``` ## 数据范围与提示 【样例1说明】 例如，在位置 0 和 7 各放置一块防水布，就可以完全覆盖这座桥。 【数据范围】 - 所有输入值都是整数。 - $1 ≤ N ≤ 10^5$ - $1 ≤ W ≤ L ≤ 10^18$ - $0 ≤ a_1 < a_2 < ... < a_N ≤ L-W$ ## 题目来源 ARC134A
提交提交记录统计露一手!