一辆汽车加满油后可行驶n公里。旅途中有若干个加油站。设计一个有效算法,指出应在哪些加油站停靠加油,使沿途加油次数最少。输入格式:第一行有2个正整数n和k (k<=1000 ),表示汽车加满油后可行驶n公里,且旅途中有k个加油站。第二行有k+1个整数,表示第k 个加油站与第k-1个加油站之间的距离。第О个加油站表示出发地,汽车已加满油。第k+1个加油站表示目的地。输出格式:输出最少加油次数。如果无法到达目的地,则输出“No Solution!"c++实现具体代码
时间: 2024-02-05 17:11:48 浏览: 24
以下是使用贪心算法实现的C++代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<int> distances(k + 1);
for (int i = 0; i <= k; i++) {
cin >> distances[i];
}
int count = 0; // 加油次数
int current = 0; // 当前位置
int remain = n; // 剩余油量
for (int i = 0; i < k; i++) {
int d = distances[i + 1] - distances[i]; // 到下一个加油站的距离
if (d > remain) { // 无法到达下一个加油站
if (remain < n) { // 如果当前有油,则加油
remain = n;
count++;
} else { // 否则无法到达目的地
cout << "No Solution!";
return 0;
}
}
remain -= d; // 行驶到下一个加油站
}
cout << count;
return 0;
}
```
算法思路:
从出发地开始,每到一个加油站时,计算到下一个加油站的距离,如果剩余油量不足以到达下一个加油站,则在当前加油站加满油,并将加油次数加一。如果无法到达目的地,则输出"No Solution!"。
相关推荐
![java](https://img-home.csdnimg.cn/images/20210720083646.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![application/x-rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)