2758: T2 开车
内存限制:128 MB
时间限制:1.000 S
评测方式:文本比较
命题人:
提交:31
解决:2
题目描述
Moc 最近花费了 $5000$ 金币,预定了 ta 最喜欢的小电车。
作为一个做梦学家,Moc 已经开始幻想将来开车从家里去数千公里之外的城市了。
假如 Moc 的家位于水平数轴上,可以认为数轴由编号为 $1$ 到 $n$ 的点组成,相邻的城市间隔 $1$ KM,家的编号为 $1$。现在 Moc 想开车从家里前往位于 $n$ 点的城市,但是,Moc 的电车并没有足够的电量一口气开到 $n$ 点,需要停在路途之中的充电站充电。
已知有 $x$ 个充电站,分别位于编号 $a_1, a_2, \ldots, a_x$ 的位置(这些位置严格递增),每个充电站都能将电车的电量充满。Moc 的电车最大电量最多能行驶 $y$ KM,其中 $y$ 是一个给定的正整数,请问 Moc 从编号为 $1$ 的家出发到达编号为 $n$ 的城市最少需要充多少次电。
注意:Moc 的家和目的地城市 $n$ 不设有充电站,且假设电车初始已充满电,数据保证可以开到终点。
作为一个做梦学家,Moc 已经开始幻想将来开车从家里去数千公里之外的城市了。
假如 Moc 的家位于水平数轴上,可以认为数轴由编号为 $1$ 到 $n$ 的点组成,相邻的城市间隔 $1$ KM,家的编号为 $1$。现在 Moc 想开车从家里前往位于 $n$ 点的城市,但是,Moc 的电车并没有足够的电量一口气开到 $n$ 点,需要停在路途之中的充电站充电。
已知有 $x$ 个充电站,分别位于编号 $a_1, a_2, \ldots, a_x$ 的位置(这些位置严格递增),每个充电站都能将电车的电量充满。Moc 的电车最大电量最多能行驶 $y$ KM,其中 $y$ 是一个给定的正整数,请问 Moc 从编号为 $1$ 的家出发到达编号为 $n$ 的城市最少需要充多少次电。
注意:Moc 的家和目的地城市 $n$ 不设有充电站,且假设电车初始已充满电,数据保证可以开到终点。
输入
第一行包含三个正整数 $n, x, y$,分别表示目的地城市的编号、充电站的数量和电车单次充满电后能行驶的最大距离。
第二行包含 $x$ 个由空格分隔的正整数 $a_1, a_2, \ldots, a_x$,表示每个充电站的位置。保证 $1 < a_1 < a_2 < \ldots < a_x < n$。
第二行包含 $x$ 个由空格分隔的正整数 $a_1, a_2, \ldots, a_x$,表示每个充电站的位置。保证 $1 < a_1 < a_2 < \ldots < a_x < n$。
输出
输出一个整数,表示 Moc 从家到达目的地最少需要充电的次数。
样例输入 复制
10 3 4
3 5 7
样例输出 复制
2
提示
**【样例解释】**
Moc 的电车可以行驶 $4$ KM,因此可以先从家(点 $1$)出发直接行驶到点 $4$。但由于第一个充电站在点 $3$,在电量耗尽前需要在这里进行第一次充电。充完电后,Moc 可以继续行驶到点 $7$,在此进行第二次充电。之后,Moc 可以直接开到终点(点 $10$)而不需要再充电。
# Limitation
- 对于 $50\%$ 的数据,有 $n \leq 10^3$。
- 对于 $100\%$ 的数据,保证 $2 \leq n \leq 10^5$,$1 \leq x < n$,$1 \leq y < n$,且 $1 < a_1 < a_2 < \ldots < a_x < n$。
Moc 的电车可以行驶 $4$ KM,因此可以先从家(点 $1$)出发直接行驶到点 $4$。但由于第一个充电站在点 $3$,在电量耗尽前需要在这里进行第一次充电。充完电后,Moc 可以继续行驶到点 $7$,在此进行第二次充电。之后,Moc 可以直接开到终点(点 $10$)而不需要再充电。
# Limitation
- 对于 $50\%$ 的数据,有 $n \leq 10^3$。
- 对于 $100\%$ 的数据,保证 $2 \leq n \leq 10^5$,$1 \leq x < n$,$1 \leq y < n$,且 $1 < a_1 < a_2 < \ldots < a_x < n$。