汽车加满油，可以跑n公里。从起点到终点有若干个加油站。问如何加油，使得加油次数最少？设计一个贪心算法。

这是一个经典的贪心算法问题，可以使用贪心算法来解决。

首先，我们需要找到一个贪心策略，即每次都加满油。这样做的原因是，加满油可以使得车辆行驶的里程数最大化，从而减少加油的次数。

其次，我们需要在到达下一个加油站之前，尽可能地行驶更远的距离。这样做的原因是，如果在中途就加油了，会浪费掉一部分油的储备，从而导致加油的次数增多。

最后，我们需要在到达每一个加油站时，判断是否需要加油。如果当前的油量无法到达下一个加油站，就必须在当前的加油站加油。

基于上述贪心策略，可以得到下面的贪心算法：

1. 初始化当前的油量为0，加油次数为0，下一个加油站的索引为0；
2. 循环，直到到达终点为止：
1. 如果当前油量可以到达下一个加油站，就继续前进；
2. 如果当前油量无法到达下一个加油站，就在当前的加油站加油，并将加油次数加1，同时更新当前油量；
3. 如果已经到达了最后一个加油站，就直接到达终点。

这个算法的时间复杂度是O(n)，其中n是加油站的个数。

相关问题

一辆汽车加满油后可行驶 n公里。旅途中有若干个加油站。设计一个有效算法，指出应 在哪些加油站停靠加油，使沿途加油次数最少。

这是一道经典的贪心算法问题。我们可以从起点开始，选择要经过的第一个加油站，使得它可以到达的最远距离为当前加满油后能行驶的最大距离，然后在这个加油站进行加油。接着，以这个加油站为起点，继续选择后续能到达的最远加油站，重复上述步骤，直到到达终点。

举个例子，假设汽车加满油可行驶500公里，旅途中有3个加油站，它们分别位于起点100公里处、中间200公里处和终点400公里处。从起点出发时，我们可以选择第一个加油站，因为到达第二个加油站需要行驶的距离是200公里，超过了当前汽车的最大行驶距离。然后，在第一个加油站加满油之后，可以行驶到第三个加油站，因此我们不需要在第二个加油站再进行加油。

通过这种方式，我们可以保证沿途加油次数最少。

一辆加满油的汽车欲行驶到m公里外的终点，旅途中有若干加油站，并且每个加油站距离起点的公里数已知，汽车加满油后可行驶n公里。如何用最少的加油次数到达目的地。给出c++代码

以下是使用贪心算法解决该问题的C++代码：

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 1000;
int pos[MAXN+1]; // 记录每个加油站距离起点的公里数

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= k; i++) {
        cin >> pos[i];
    }
    pos[k+1] = m; // 终点也视为加油站
    sort(pos+1, pos+k+1); // 将加油站按距离排序

    int ans = 0, now = 0; // ans为加油次数，now为当前所在位置
    while (now < m) { // 还未到达终点
        int maxd = now + n; // 计算能到达的最远距离
        int p = lower_bound(pos+1, pos+k+2, maxd) - pos - 1; // 找到最远的加油站
        if (p == 0 || pos[p] == now) { // 无法到达下一个加油站
            cout << "-1" << endl;
            return 0;
        }
        ans++; // 加油次数加1
        now = pos[p]; // 移动到下一个加油站
    }
    cout << ans << endl;
    return 0;
}

该算法的时间复杂度为$O(k\log k)$，其中$k$为加油站数量。