题目
图1. 题目要求
思路
- 题目要求最少加油次数，为了加油次数最少，我们需要考虑下面的问题
- 什么时候加油能使得加油次数最少？
当油用完的时候加油。
具体实现：判断到下一个加油站的距离和此时油量的大小，如果油量大于距离则还不用加油，如果油量小于距离则需要加油。 - 在哪个加油站加油可以使得加油的次数最少？
在油量最大的加油站加油。
具体实现：可以使用一个数据结构保存经过的加油站的油量，当油量不够到下一站的时候从其中取出油量最大的值。
- 怎么解决上面的两个问题
-
对问题进行建模：图1. 问题建模
在数轴上的点表示加油站。
图2. 思路分析
图3. 流程分析
代码实现
bool cmp(const std::pair<int, int> &a, const std::pair<int, int> &b)
{
return a.first > b.first;
}
int getMinimumStop(std::vector<std::pair<int, int>> &stop, int P, int L)
{
int minimumStop = 0;
std::priority_queue<int> Q; // 用来存放油量的最大堆
stop.push_back(std::make_pair(0, 0)); // 将终点作为一个停靠点添加到stop中
std::sort(stop.begin(), stop.end(), cmp); // 将停靠点到终点的距离大小排序
for (int i = 0; i < stop.size(); i++) { // 遍历各个停靠点
int distance = L - stop[i].first;
while (!Q.empty() && P < distance) { // 如果剩余油量不够到下一个加油站则要加油
P += Q.top();
Q.pop();
minimumStop++;
}
if (Q.empty() && P < distance) {
return -1;
}
P = P - distance;
L = stop[i].first;
Q.push(stop[i].second);
}
return minimumStop;
}
