自転車走
题意翻译
题目描述
制作一个游戏,沿着直线从初始位置跑到目的地。
在这个游戏中,自行车可以行驶的地方受到限制。把可以行驶的地方称为地面。地面由N个区间ai,bi组成。假设到初始位置的距离为x,如果在任意i中满足ai<=x<=bi, 这就意味着自行车可以在该点行驶。
自行车以恒定速度自动运行,但如果自行车在地面上行驶,玩家可以使自行车跳起。当玩家跳跃时,自行车在那一刻跳到空中并降落在离跳跃点距离为W的位置上。在空中飞行时,你可以穿过不为地面的部分,但降落点必须是地面。此外,降落点不能超过目的地。在一次游戏中可以多次跳跃,并且在着陆后可以立刻再次跳跃。完成跳跃后,自行车将再次自动运行。
你不能跑到地面以外的任何点上,请你找到到达目的地所需的最小跳跃次数。如果你怎么跳都无法达到目的地,输出-1。
图H是输入样例1中到达目的地的示例。
说明
输入方式
用以下方式输入。
输出方式
输出使自行车到达所需的最小跳跃次数。如果无法到达,则输出-1。
制约
1<=N<=10^5
1<=L<=10^9
1<=W<=L
ai<bi
bi<ai+1
a1=0,bN=L
所有输入都是整数
感谢@sunyy 提供的翻译
题目描述
[problemUrl]: https://atcoder.jp/contests/kupc2014/tasks/kupc2014_h