871. Minimum Number of Refueling Stops
程序员文章站
2024-02-14 09:45:58
...
难得,自己想出来的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;
}
};
如果有一个站点到达不了,就加前面的最多的一个。
上一篇: unity shader 学习笔记
下一篇: oracle 常用日期时间相关函数