🚗 最少加油次数

📘 题目来源

📄 题目描述

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

如果无法到达目的地，则输出 "No Solution!"。

🔢 输入格式

• 第一行包含两个正整数 $n$ 和 $k$（$1 \le k \le 1000$）：
  • $n$：表示汽车加满油后可行驶的最大距离。
  • $k$：表示途中有 $k$ 个加油站。
• 第二行包含 $k+1$ 个正整数，表示：
  • $a\_1, a\_2, \dots, a\_{k+1}$：第 $i$ 个加油站到第 $i-1$ 个加油站之间的距离（第 $0$ 个加油站为出发地，$k+1$ 号加油站为目的地）。

📤 输出格式

• 输出一个整数：表示从出发地到目的地所需的最少加油次数；
• 如果无法到达目的地，输出 No Solution!

💡 输入样例

7 7
1 2 3 4 5 1 6 6

✅ 输出样例

4

📘 样例解释

• 每次汽车最多走 $7$ 公里。
• 途中依次停靠在加油站 $1, 3, 5, 6$，刚好覆盖总路程 $28$ 公里。
• 一共加油 $4$ 次。

🧠 思路简述

本题是典型的 贪心算法 问题。

从出发地开始，使用如下策略：

1. 当前油量允许行驶的最远距离内，寻找最远可达的加油站。
2. 若在这个范围内找不到加油站，说明目的地无法到达。
3. 每次跳到最远可达的加油站，直到到达终点。