問題描述：

一輛汽車加滿油后可以行駛n千米。旅途中有若干個加油站，為了使沿途加油的次數減少，設計一個算法，輸出最好的加油方案。
例如，假設沿途有9個加油站，總路程100千米，加滿油后汽車可以行駛的最遠距離為20千米。

汽車加油位置描述： 以出發點為0點，終點為100。加油站分別位于10、20、35、40、50、65、75、85和90，以距離遠近依次標號為1、 2、...9.

問題分析：

因為要讓車加油次數盡可能的少，那么我們需要讓車每次盡可能的開遠一點再加油。這便是我們策略。

• 我們首先需要假設讓車開出最遠的距離n千米，找出距離最近且靠近出發點的一個加油站進行加油。
• 而當加完油之后，車便又是滿油狀態，只需要接著讓車按照上一條思路，找到接下來如何安排加油站。
• ！！！本題只考慮有解情況，即不會出現兩加油站之間最大距離大于車輛滿油最大行駛距離。

問題實現：

我們把加油站的地點存在數組中。

• s用于表示全長，將0視為起點,num為加油站數量,n為最遠行駛距離。
• i表示的是當前車開到的加油站在數組a中序號（從0開始排）。
• count表示加油次數，distance表示當前車行駛的總路程，drive表示上次加油后已行駛的距離。
• while循環中if表示的是目前車不能在不加油的情況下開到下一個加油站，所以在這個加油站加一次油，加完油之后一定可以開到下一個加油站，所以drive的值變為下一加油站到這一加油站的距離；else中則是可以在本站不加油的情況下開到下一加油站。所以drive得在原本基礎上再加上一段行駛距離。

#include<iostream> using namespace std;int main(){int s = 100, num = 9, n = 20; //s用于表示全長，將0視為起點,num為加油站數量,n為最遠行駛距離。int a[] = {10, 20, 35, 40, 50, 65, 75, 85, 90}; //數組a存儲加油站地點。//上述變量直接給出值。int count = 0, distance = 0; int i = 0, drive = a[0];while(distance<100 && i<=num-1){ if( (a[i+1]-a[i]) > (n-drive) ){cout<<"在第"<<i+1<<"加油站，加了一次油"<<endl; distance = a[i+1];drive = a[i+1]-a[i];i++;count++; }else {distance = a[i+1];drive += a[i+1]-a[i];i++;}}cout<<"一共加了"<<count<<"次油~"<<endl;return 0; }

總結

以上是生活随笔為你收集整理的加油站问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。