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

### 回答1：
这是一个经典的贪心算法问题。我们可以从起点开始，每次选择能够到达的最远的加油站进行加油。如果当前加油站无法到达下一个加油站，则在当前加油站加满油后继续前行。重复这个过程直到到达终点。

具体实现时，我们可以使用一个变量来记录当前车内油量，每到达一个加油站就更新这个变量。如果当前油量无法到达下一个加油站，则在当前加油站加满油后继续前行，并将加油次数加一。

需要注意的是，如果有多个加油站能够到达的距离相同，则应该选择最靠前的那个加油站进行加油，以最大程度地减少加油次数。

总之，这个问题的解决方法是贪心算法，每次选择能够到达的最远的加油站进行加油，直到到达终点。

### 回答2：
这道题目可以用贪心算法来解决。我们可以考虑从起点出发，每途经一个加油站，都计算一下到下一个加油站之间需要消耗的油量。

假设当前行驶到加油站 i，我们需要计算出能否到达下一个加油站 j。如果能到达，我们就继续前进；如果无法到达，我们就在当前加油站加满油。这样做可以保证在沿途的每一个加油站都尽可能地加满油，从而保证油量始终充足。

如果在当前状态下无法到达下一个加油站，我们选择在当前加油站加满油之后再向前行驶。这样做可以保证在当前状态下，能够行驶的最远距离最大化。

具体实现时，我们可以考虑记录两个变量：当前加油站的编号 i，以及从起点到当前加油站之间已经行驶的距离 D。遍历整个加油站序列，对于每一个加油站 j，我们都计算一下从 i 出发到 j 之间需要消耗的油量，如果 D + (j-i) <= n，则说明能够到达 j；如果无法到达，则说明前一段路需要加满油，我们就在 i 处加满油，并更新 D 的值。

具体实现时，我们可以使用贪心算法的思想，每次选择能到达的最远的加油站作为下一个停靠点，这样可以保证加油次数最少。实际上，这个算法的时间复杂度是 O(n)，非常高效。

### 回答3：
这是一个经典的贪心算法问题，可以用贪心策略来解决。具体的算法步骤如下：

1. 设当前汽车在加油站 i，已经走过了距离 dis，当前油量为 oil。
2. 在当前加油站 i 的下一个加油站 j 中，找到满足 dis + oil >= jdis 的最小 j。
3. 如果当前没有合适的加油站，则停在能够到达的最近的加油站进行加油。
4. 以步骤 2 找到的加油站为下一个加油站，不断重复步骤 2 和 3，直到到达终点。

这个算法的正确性依赖于贪心策略的正确性，即每次选择能够到达的最远的加油站，可以使得沿途加油次数最少。证明可以通过反证法得到：假设选择了一个不是最远的加油站进行加油，那么必须在后面的某个时刻再次加油，这样需要加油的次数就增加了。选择最远的加油站可以最大限度地延长加油间隔，从而使得沿途加油次数最少。

总之，这个算法可以在 O(n) 的时间复杂度内解决问题，是一个高效而且正确的解决方案。