贪心算法-最优加油方法贪心算法-最优加油方法

题目
文章图片
图1. 题目要求思路

题目要求最少加油次数，为了加油次数最少，我们需要考虑下面的问题

什么时候加油能使得加油次数最少？
当油用完的时候加油。
具体实现：判断到下一个加油站的距离和此时油量的大小，如果油量大于距离则还不用加油，如果油量小于距离则需要加油。
在哪个加油站加油可以使得加油的次数最少？
在油量最大的加油站加油。
具体实现：可以使用一个数据结构保存经过的加油站的油量，当油量不够到下一站的时候从其中取出油量最大的值。

怎么解决上面的两个问题

对问题进行建模：
文章图片
图1. 问题建模
【贪心算法-最优加油方法】在数轴上的点表示加油站。

文章图片
图2. 思路分析

文章图片
图3. 流程分析

代码实现

bool cmp(const std::pair &a, const std::pair &b) { return a.first > b.first; } int getMinimumStop(std::vector> &stop, int P, int L) { int minimumStop = 0; std::priority_queue 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; }