一辆加满油的汽车欲行驶到m公里外的终点,旅途中有若干加油站,并且每个加油站距离起点的公里数已知,汽车加满油后可行驶n公里。如何用最少的加油次数到达目的地。给出c++代码
时间: 2024-01-03 11:07:12 浏览: 83
汽车加油问题 对于给定的n和k个加油站位置,编程计算最少加油次数。
4星 · 用户满意度95%
以下是使用贪心算法解决该问题的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$为加油站数量。
阅读全文