汽车油箱容量 今天我们来看一道加油最少时间算法题。假设你要从城市A开车到城市B，途中有多个加油站，你的车的油箱容量为 C，起始时刻油箱已经有 P 的油。每个加油站提供无限量的油，但是加满油的时间不同，加满油所需时间为 Ti。同时，每公里汽车消耗的油量都是一样的，为 D。从起点到终点的距离为 L，你需要选择一个最佳的加油方案，让你在最短的时间内到达终点。请问最短需要多长时间？
思路：
这是一道经典的贪心算法问题。我们需要做的是在每个加油站都加满油，同时保证下一站能够到达。我们用一个变量 pos 表示当前车子的位置，用一个变量 tank 表示当前的油量，用一个变量 ans 表示已经用的时间。我们逐个遍历每个加油站，如果这个加油站到当前位置的距离大于车子当前的油量，说明需要加油了，我们在上一站加满油，更新当前位置和油量，同时记录下加油花费的时间。如果到达终点后还没有加满油，就在终点加满油。当然，如果有一站加不下满油，那么车就无法到达终点，返回 -1。
代码实现：
时间复杂度为 O(nlogn)，其中 n 为加油站的个数。
发布评论