这题本质是一个经典的“最小费用加油”问题,使用贪心算法即可。
已知:
多多驾驶电动车从起点0出发,目的地距离为L公里。电动车满电时可行驶C公里,即电池容量为C公里续航。沿途有n个充电站,第i个充电站位于距离起点d公里处,充电价格一公里pi
多多可以在任何充电站进行充电,充电量可以任意,但不能超过电池总容量
已知多多出发时电池处于满电状态。请你帮多多规划充电策略,求出到达目的地所需的最少充电费用。如果无论如何都无法到达目的地,请输出−1。
第一行包含三个整数L,C,n别表示目的地距离、满电续航公里数、充电站的数量。(1<=L<=1e9,1<=C<=1e9,1<=n<=5000)
接下来n行,每行包含两个整数d,p,分别表示第i个充电站距离起点的距离以及该站的充电单价。(1<=di≤di+1<L,1<=pi<=1e9)
输出一个整数,表示到达目的地所需的最少充电总费用。如果无法到达,输出−1。
输入
20 10 3
4 5
9 2
15 6
输出
24
说明
起点满电(续航10)
开至距离9的充电站,此时剩余电量1
在距离9的充电站充9公里电量达到满电,花费9∗2=18,此时电量10
开至距离15的充电站,消耗6,此时剩余电量4。
在距离15的充电站充1公里电量,花费1∗6=6,此时电量5。
刚好开到终点20(消耗5),剩余电量0.
总费用: 18+6=24
输入
20 5 1
10 5
输出
-1
说明
满电只能跑5公里,还没跑到第一个充电站就没电了,所以无法到达。