欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

871. Minimum Number of Refueling Stops

程序员文章站 2024-02-14 09:45:58
...

871. Minimum Number of Refueling Stops

难得,自己想出来的hard。

class Solution {
public:
    int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
        int remain = startFuel;
        priority_queue<int> pq;//留下的之前没有加的,不是遇到一个讨论现在要不要加,而是之后需要了再加
        int cnt = 0;
        int lastPos = 0;
        stations.push_back(vector<int>{target, 0});
        for (auto& station : stations) {
            int dist = station[0] - lastPos;
            lastPos = station[0];
            /*if (remain >= dist) {
                remain -= dist;
                pq.push(station[1]);
            } else {*/
                while (remain < dist) {
                    if (pq.empty())
                        return -1;
                    remain += pq.top();
                    pq.pop();
                    ++cnt;
                }
                remain -= dist;
                pq.push(station[1]);
            //}
        }
        return cnt;
    }
};

如果有一个站点到达不了,就加前面的最多的一个。