871. 最低加油次数

原题链接:871. 最低加油次数

 

solution:

        本题考察优先队列+贪心。题目的意思是相当于在行驶的过程中把途径的汽油全部携带在身上，如果汽车无法抵达下一个加油站则把汽油最多的那个油桶加上，最后统计加油的次数。

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        if(stations.size() == 0) {  //没有加油站，能否抵达只取决于初始油量
            if(startFuel >= target) return 0;
            else return -1;
        }

        priority_queue<int,vector<int>,less<int>> heap; //定义大根堆
        int miles = startFuel;  //可以抵达的距离
        int res = 0;//加油次数
        for(int i = 0;i < stations.size();i++) {
            if(miles >= target) return res;  //可以抵达跳出循环
            while(miles < stations[i][0]) {    //当公里数不够抵达下一个加油站的时候
                if(heap.empty()) return -1; //没有汽油可加,不能抵达
                auto oil = heap.top();
                heap.pop();
                miles += oil;
                res++;
            }
            heap.push(stations[i][1]);
        }
        //已经携带了全部的汽油,但还没抵达终点进行特判
        while(miles < target) {
            if(heap.empty()) return -1;
            auto oil = heap.top();
            heap.pop();
            miles += oil;
            res++;
        }
        return res;
    }
};