Leetcode（871）-最低加油次数

汽车从起点出发驶向目的地，该目的地位于出发位置东面 target 英里处。

沿途有加油站，每个 station[i] 代表一个加油站，它位于出发位置东面 station[i][0] 英里处，并且有 station[i][1] 升汽油。

假设汽车油箱的容量是无限的，其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。

当汽车到达加油站时，它可能停下来加油，将所有汽油从加油站转移到汽车中。

为了到达目的地，汽车所必要的最低加油次数是多少？如果无法到达目的地，则返回 -1 。

注意：如果汽车到达加油站时剩余燃料为 0，它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0，仍然认为它已经到达目的地。

示例 1：

输入：target = 1, startFuel = 1, stations = []

输出：0

解释：我们可以在不加油的情况下到达目的地。

示例 2：

输入：target = 100, startFuel = 1, stations = [[10,100]]

输出：-1

解释：我们无法抵达目的地，甚至无法到达第一个加油站。

示例 3：

输入：target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]

输出：2

解释：

我们出发时有 10 升燃料。

我们开车来到距起点 10 英里处的加油站，消耗 10 升燃料。将汽油从 0 升加到 60 升。

然后，我们从 10 英里处的加油站开到 60 英里处的加油站（消耗 50 升燃料），

并将汽油从 10 升加到 50 升。然后我们开车抵达目的地。

我们沿途在1两个加油站停靠，所以返回 2 。

思路：如果采用暴力求解，肯定会超时，这里要用贪心的思路，

我们结合下实际情况：我们想象下，车子在还有油时，不断向前行驶，每遇到一个加油站i时，都把Bi量的油放在车上，注意这并不是给油缸加油，只是相当于放在后备箱了，然后在车子没有油时，从后备箱选择一个油量最大的进行加油，这样不断重复，在后备箱中已经没有油，但是还没到终点，那么就不能到终点了，也就是输出-1。比较类似贪心，每次选择一个对当前情况最有利的情况。

在进行选择后备箱的油时，当然可以使用循环不断比较后获得最大油量，可是没必要，我们可以使用C++的STL库中的一个数据结构---优先队列priority_queue,每次把油加入后备箱时，都会自动按int类型键值从大到小排序，然后每次从后备箱取油时，会自动返回最大油量.

int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations)

{

    //ans表示最后结果，即最小加油次数

    //pos表示当前卡车位置

    //tank表示油缸中油的数量

    //que优先队列中存放之前能通过的各个加油站的最大加油量Bi

    priority_queue<pair<int,int> > que;

    int ans=0,pos=0,tank=startFuel;

    vector<int> c;

    c.push_back(target);//这里要把终点也算进去

    c.push_back(0);//0代表终点没有油桶

    stations.push_back(c);

    for(int i=0;i<stations.size();i++)

    {

        int curDist=stations[i][0]-pos;   //curDist表示到达下一个临时终点(加油站)的距离

        while(curDist>tank)      //当前油不够到下一个终点

        {

            if(que.empty())

            {

                return -1;

            }

            pair<int,int> temp=que.top();

            que.pop();

            tank+=temp.first;         //不断加油,直到能到达下一个终点

            ans++;

        }

        tank-=curDist;          //跑到下一个终点，消耗 curDist数量的油

        pos=stations[i][0];               //到达下一个加油站，取得该加油站的油，放在优先队列中，以便后面使用

        que.push(make_pair(stations[i][1],i));  

    }

    return ans;

}

这里二维vector的插入数据，原理如下：我们在动态申请二维数组vector的时候，一般会用vector<vector<int> >a(4,vector<int>(2));然后再往里面push值。它之所以是二维数组，是因为它把每一行都用vector存储起来，可以认为a里面存放的是一个个行的vector，而每个vector中push了两个值。那我们如果要插入一行的话，也要以vector<int>的形式push进去，那需要提前建一个vector，然后往里面打两个值，再push到我们的二维vector中。

巴特西

Leetcode（871）-最低加油次数

最新文章

热门文章