【大根堆】【C++算法】871 最低加油次数

简介: 【大根堆】【C++算法】871 最低加油次数

作者推荐

【动态规划】【map】【C++算法】1289. 下降路径最小和 II

本文涉及知识点

大根堆 优先队列

LeetCode:871最低加油次数

汽车从起点出发驶向目的地,该目的地位于出发位置东面 target 英里处。

沿途有加油站,用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处,并且有 fueli 升汽油。

假设汽车油箱的容量是无限的,其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时,它可能停下来加油,将所有汽油从加油站转移到汽车中。

为了到达目的地,汽车所必要的最低加油次数是多少?如果无法到达目的地,则返回 -1 。

注意:如果汽车到达加油站时剩余燃料为 0,它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0,仍然认为它已经到达目的地。

示例 1:

输入:target = 1, startFuel = 1, stations = []

输出:0

解释:可以在不加油的情况下到达目的地。

示例 2:

输入:target = 100, startFuel = 1, stations = [[10,100]]

输出:-1

解释:无法抵达目的地,甚至无法到达第一个加油站。

示例 3:

输入:target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]

输出:2

解释:

出发时有 10 升燃料。

开车来到距起点 10 英里处的加油站,消耗 10 升燃料。将汽油从 0 升加到 60 升。

然后,从 10 英里处的加油站开到 60 英里处的加油站(消耗 50 升燃料),

并将汽油从 10 升加到 50 升。然后开车抵达目的地。

沿途在两个加油站停靠,所以返回 2 。

参数:

1 <= target, startFuel <= 109

0 <= stations.length <= 500

1 <= positioni < positioni+1 < target

1 <= fueli < 109

分析

加油站的位置已经按升序排序。

iCan 记录加油i次后,能到达的最远位置。i 取值区间[0,stations.length]

第i+1次加油,一定是iPreCan(第i次加油的iCan)能到达且没有加油,油量最大的加油站。

如果没有到达终点,且无油可加返回-1。

代码

核心代码

class Solution {
public:
  int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
    int iCan = startFuel;
    priority_queue<int> canAdd;
    int j = 0;
    for (int i = 0; i < stations.size(); i++)
    {
      if (iCan >= target)
      {
        return i;
      }
      //canAdd能加油的加油站
      while ((j < stations.size()) && (stations[j][0] <= iCan))
      {
        canAdd.emplace(stations[j++][1]);
      }
      if (canAdd.empty())
      {
        return -1;
      }
      iCan += canAdd.top();
      canAdd.pop();
    }
    return (iCan >= target) ? stations.size() : -1;
  }
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{ 
  int target,  startFuel;
  vector<vector<int>> stations;
  {
    Solution sln;
    target = 1, startFuel = 1, stations = {};
    auto res = sln.minRefuelStops(target, startFuel, stations);
    Assert(res, 0);
  }
  {
    Solution sln;
    target = 100, startFuel = 1, stations = { {10,100} } ;
    auto res = sln.minRefuelStops(target, startFuel, stations);
    Assert(res, -1);
  }
  {
    Solution sln;
    target = 100, startFuel = 10, stations = { {10, 60},{20, 30},{30, 30},{60, 40} };
    auto res = sln.minRefuelStops(target, startFuel, stations);
    Assert(res, 2);
  } 
  {
    Solution sln;
    target = 100, startFuel = 50, stations = { {25, 25},{50, 50} };
    auto res = sln.minRefuelStops(target, startFuel, stations);
    Assert(res, 1);
  }
}

2023年1月第一版

class Solution {

public:

int minRefuelStops(int target, int startFuel, vector<vector>& stations) {

std::unordered_map<int,int> preDp;

preDp[0] = startFuel;

int iPrePos = 0;

for (auto& v : stations)

{

std::unordered_map<int, int> dp;

for (auto& pre : preDp)

{

const int iHasFuel = pre.second - (v[0] - iPrePos);

if (iHasFuel < 0 )

{

continue;

}

Add(dp, pre.first, iHasFuel);

Add(dp, pre.first+1, iHasFuel + v[1]);

}

preDp.swap(dp);

iPrePos = v[0];

}

int iMinNum = INT_MAX;

for (auto& pre : preDp)

{

const int iHasFuel = pre.second - (target - iPrePos);

if (iHasFuel < 0)

{

continue;

}

iMinNum = min(iMinNum, pre.first);

}

return (INT_MAX == iMinNum) ? -1 : iMinNum;

}

void Add(std::unordered_map<int, int>& dp, int iNum, int iFuel)

{

iFuel = min(iFuel, 1000 * 1000 * 1000);

auto it = dp.find(iNum);

if (dp.end() == it)

{

dp[iNum] = iFuel;

}

else

{

it->second = max(it->second, iFuel);

}

}

};

2023年1月 第二版

class Solution {

public:

int minRefuelStops(int target, int startFuel, vector<vector>& stations) {

m_iFuel = startFuel;

for (auto& v : stations)

{

Add(v[0]);

if (m_iFuel < v[0])

{

return -1;

}

m_qFuel.push(v[1]);

}

Add(target);

if (m_iFuel < target)

{

return -1;

}

return stations.size() - m_qFuel.size();

}

void Add(int iNeedFuel)

{

while (m_qFuel.size() && (m_iFuel < iNeedFuel))

{

m_iFuel += m_qFuel.top();

m_qFuel.pop();

}

}

std::priority_queue m_qFuel;

int m_iFuel;

};

2023年 8月版

class Solution {

public:

int minRefuelStops(int target, int startFuel, vector<vector>& stations) {

stations.emplace_back(vector{target, 0});

int iRet = 0;

std::multiset setCanAdd;

int iHas = startFuel;

for (const auto& v : stations)

{

while (setCanAdd.size() && (iHas < v[0]))

{//油不够,需要加油

iHas += *setCanAdd.rbegin();

setCanAdd.erase(std::prev(setCanAdd.end()));

iRet++;

}

if (iHas < v[0])

{

return -1;

}

setCanAdd.emplace(v[1]);

}

return iRet;

}

};


相关文章
|
1月前
|
算法 测试技术 C++
【动态规划算法】蓝桥杯填充问题(C/C++)
【动态规划算法】蓝桥杯填充问题(C/C++)
|
1月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
415 0
高精度算法(加、减、乘、除,使用c++实现)
|
1月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
22 0
|
1月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
1月前
|
人工智能 算法 C++
一篇带你速通前缀和算法(C/C++)
一篇带你速通前缀和算法(C/C++)
|
1月前
|
存储 算法 C++
弗洛伊德(Floyd)算法(C/C++)
弗洛伊德(Floyd)算法(C/C++)
|
1月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)