算法設計 加油問題

1. 問題描述
一個旅行家想駕駛汽車從城市A到城市B（設出發時油箱是空的）。給定兩個城市之間的距離dis、汽車油箱的容量c、每升汽油能行駛的距離d、沿途油站數n、油站i離出發點的距離d[i]以及該站每升汽油的價格p[i],i=1,2,…,n。設d[1]=0<d[2]<…<d[n]。要花最少的油費從城市A到城市B，在每個加油站應加多少油，最少花費為多少？
2. 具體要求
Input
輸入的第一行是一個正整數k，表示測試例個數。接下來幾行是k個測試例的數據，每個測試例的數據由三行組成，其中第一行含4個正整數，依次為A和B兩個城市之間的距離d1、汽車油箱的容量c（以升為單位）、每升汽油能行駛的距離d2、沿途油站數n (1<=n<=200)；第二行含n個實數d1, d2 ,…, dn，表示各油站離出發點的距離（d1=0）；第三行含n個實數p1, p2 ,…, pn，表示各油站每升汽油的價格。同一行的數之間用一個空格隔開。
Output
對于每個測試例輸出一行，含一個實數，表示從城市Ａ到城市Ｂ所要花費的最少油費（輸出的結果精確到小數點后一位）。若問題無解，則輸出“No Solution”。
3. 測試數據
Sample Input
2
1500 50 10 4
0 300.0 800.0 1200.0
4.0 5.0 4.0 4.5
1000 40 10 3
0 500.0 750.0
4.5 5.0 4.2

Sample Output
640.0
No Solution

思路：
從當前加油站開始，每次選擇的加油站符合：

當前站加滿油后可以到達，如果不等到達則可以認為此題無解

在所有可以到達的加油站中選擇價格最低的

如果當前站的價格最低就加滿油，否則就使加的油剛好可以到達價格最低的加油站

終點站特殊考慮

代碼：

/// <summary> /// 尋找最好的加油站和下一個要去的加油站 /// </summary> /// <param name="bestStation">最好的加油站</param> /// <param name="nextStation">下一個要去的加油站</param> /// <param name="d"></param> /// <param name="p"></param> /// <param name="n"></param> /// <param name="curStation"></param> /// <param name="c"></param> /// <param name="d2"></param> void bestNextStation(int& bestStation, int& nextStation,float* d, float* p, int n, int curStation, int c, int d2) {bestStation = curStation;int i = curStation + 1;for (; i < n; i++){if (c * d2 + d[curStation] >= d[i]) // 在當前加油站加滿油后能到達i號加油站{if (p[bestStation] >= p[i]) // 當前最好的下一個加油站的價格更貴，則切換最好的加油站{bestStation = i;}}else{break;}}if (bestStation == curStation) // 如果當前加油站就是最好的加油站{nextStation = i - 1; // 下一個加油站就是最遠能去到的加油站}else{nextStation = bestStation; // 下一個就去最好的加油站} }void test1() {int k, d1, c, d2, n; // 依次為A和B兩個城市之間的距離d1、汽車油箱的容量c（以升為單位）、每升汽油能行駛的距離d2、沿途油站數n float* d = nullptr, * p = nullptr; // d表示各油站離出發點的距離 p表示各油站每升汽油的價格cin >> k;while (k--){cin >> d1 >> c >> d2 >> n;d = new float[n];p = new float[n];for (int i = 0; i < n; i++){cin >> d[i];}for (int i = 0; i < n; i++){cin >> p[i];}float curOil = 0;int curStation = 0;float curMoney = 0;bool noSolutuon = false;while (curStation < n - 1){if (curOil * d2 + d[curStation] < d[curStation + 1]) // 剩余的油不足以到下一個加油站{if (c * d2 + d[curStation] < d[curStation + 1]) // 加滿油也無法到達下一個加油站{cout << "No Solution" << endl;noSolutuon = true;break;}else{int bestStation, nextStation;bestNextStation(bestStation, nextStation, d, p, n, curStation, c, d2);float neededOil = (d[nextStation] - d[curStation]) / d2 - curOil;if (bestStation == curStation) // 如果當前加油站就是最好的加油站{neededOil = c - curOil; // 那么加滿油}float neededMoney = neededOil * p[curStation];curOil += neededOil;curMoney += neededMoney;curOil -= ((d[nextStation] - d[curStation]) / d2); // 減去實際消耗的油curStation = nextStation;}}}if (curStation == n - 1) // 已經到達最后一個加油站了{if (c * d2 + d[curStation] < d1) // 最后一個加油站加滿油也無法到達終點{cout << "No Solution" << endl;noSolutuon = true;break;}else{float neededOil = (d1 - d[curStation]) / d2 - curOil;float neededMoney = neededOil * p[curStation];curMoney += neededMoney;}}if (!noSolutuon){cout << fixed << setprecision(1) << curMoney << endl;}delete[] d;delete[] p;} }

截圖：

總結

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

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