[贪心+优先队列]leetcode871：最低加油次数(hard)

题目：

题解：

思路：贪心队列+贪心

• 不用每经过一个站点就开始加油，应当是燃料不足以行驶到下一个加油站时，然后从优先队列中选择油量最大的油进行加油，直到能行驶到下一个站位置，在加油的同时记录经过的站点即可。

代码如下：

class Solution {
public:
    int minRefuelStops(int t, int p, vector>& st) {
        // 把终点加入站点
        st.push_back({t,0});
        // 加油次数；现在所处的位置；油箱中的汽油
        int res=0,pos=0,tank=p;
        // 存储汽油的大根堆
        priority_queue pq;
        for(auto& s:st){
            // 接下来要前进的距离
            int d = s[0] - pos;
            // 不断加油直到油量足够行驶到下一个加油站
            while(tank-d<0){
                if(pq.empty())return -1;
                tank+=pq.top();pq.pop();
                res++;
            }
            tank-=d,pos=s[0],pq.push(s[1]);
        }
        return res;
    }
};