贪心算法-最优加油方法

题目

图1. 题目要求

思路

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

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

2. 怎么解决上面的两个问题

• 对问题进行建模： 图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;
    }