AlgoMooc
← 返回题库

P5921. 开电动汽车回家过年

简单通过率 18% · 提交 89 · 通过 16
动态规划贪心排序DP

新年即将来临,小慕计划开新买的电动汽车回老家过年。 已知小慕的工作地在上海,老家在中部某城市A。 上海到城市A的距离是L公里(1 <= L <= 100000)。 小慕的电动汽车的 (1 <= P <= 100),电池最大电量也是P(假设电动汽车行驶一公里需要消耗1度电)。 如果电动车在中途电量耗尽了,将无法继续前行,也就无法到达目的地了。已知小慕出发前已经把电池充满了。 途中依次经过N (1 <= N < 10000)个充电站。 。 请问,小慕能不能顺利地回老家过年?如果可以,请输出最少需要充电多少次;如果不可以,请输出-1。

提示:带虚线的词点一下有通俗解释。

输入描述

输入的第一行为数字N。 接下来的N行,每行包含2个数并用空格隔开,分别表示Ai Bi 最后一行包括两个数L P,并用空格隔开。

输出描述

按照题目要求输出最少次数或者-1。

示例

示例 1

输入

4
4 4
5 5
11 6
15 8
25 10

输出

3

时间限制 1000 ms · 内存限制 128 MB

看不懂题目?点开图解(训练营专属)

登录后查看题目图解

题目图解为训练营学员专属内容,请先登录。

微信扫码登录还不是训练营学员?了解训练营 →
写完代码点「提交」,将对全部测试用例判题。