数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中加油站的最少次数
假设有一辆汽车，从起始位置行驶到其东边 t 英里的目的地。
沿途有许多加油站。因此，每个 station[i] 代表一个加油站，该加油站位于起始位置东边 station[i][0] 英里处，并且该加油站有 station[i][1] 升汽油。
如果汽车从一个无限大的油箱开始，最初油箱中有 startFuel 升汽油。它每行驶 1 英里消耗 1 升汽油。
当汽车到达一个加油站时，它可以停下来加油，因此现在它将加油站的所有汽油转移到汽车中。我们必须找到汽车为了到达目的地必须进行的最少加油次数？如果无法到达目的地，则返回 -1。
因此，如果输入类似于 Target = 100，startFuel = 20，stations = [10,40],[20,30],[30,20],[60,40]，则输出将为 3。最初有 10 升汽油，到达第一个加油站后，它将转移 40 升汽油，因此目前有 (0 + 40) = 40 升汽油，然后到达第三个加油站，现在转移 20 升汽油，因此当前数量为 (20+20) = 40，然后到达最后一个加油站，获取 40 升汽油，因此当前数量 (10 + 40) = 50，到目前为止，我们已经行驶了 60 英里，因此我们还需要行驶 40 英里才能到达目的地，有足够的汽油到达目标。
为了解决这个问题，我们将遵循以下步骤 -
curr := 0
对数组 st 进行排序
定义优先级队列 pq
i := 0, cnt := 0
curr := curr + fuel
当 curr < target 时，执行 -
(将 cnt 增加 1)
当 (i < st 的大小且 st[i, 0] <= curr) 时，执行 -
将 st[i, 1] 插入 pq
(将 i 增加 1)
如果 pq 为空，则 -
退出循环
curr := curr + pq 的顶部元素
从 pq 中删除元素
返回 (如果 curr >= target，则返回 cnt，否则返回 -1)
让我们看看以下实现以更好地理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minRefuelStops(int target, int fuel, vector<vector<int>> &st) {
int curr = 0;
sort(st.begin(), st.end());
priority_queue<int> pq;
int i = 0;
int cnt = 0;
curr += fuel;
while (curr < target) {
cnt++;
while (i < st.size() && st[i][0] <= curr) {
pq.push(st[i][1]);
i++;
}
if (pq.empty())
break;
curr += pq.top();
pq.pop();
}
return curr >= target ? cnt : -1;
}
};
main(){
Solution ob;
vector<vector<int>> v = {{10,40},{20,30},{30,20},{60,40}};
cout << (ob.minRefuelStops(100, 10, v));
}输入
100, 10, {{10,40},{20,30},{30,20},{60,40}}输出
3
487 次浏览
