一、題目描述
題目描述
一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設出發時油箱是空的），給定兩個城市之間的距離D1D1、汽車油箱的容量CC（以升為單位）、每升汽油能行駛的距離
D2D2、出發點每升汽油價格PP和沿途油站數NN（NN可以為零），油站ii離出發點的距離DiDi、每升汽油價格PiPi（i=1,2,…,Ni=1,2,…,N），計算結果四舍五入至小數點后兩位，如果無法到達目的地，則輸出“No Solution”，
輸入格式
第一行，D1D1，CC，D2D2，PP，NN，
接下來有NN行，
第i+1i+1行，兩個數字，油站i離出發點的距離DiDi和每升汽油價格PiPi，
輸出格式
所需最小費用，計算結果四舍五入至小數點后兩位，如果無法到達目的地，則輸出“No Solution”，
輸入輸出樣例
輸入
275.6 11.9 27.4 2.8 2 102.0 2.9 220.0 2.2
輸出
26.95
說明/提示
N≤6,其余數字≤500
二、用到的演算法思想
【貪心演算法】
三、思路
首先做如下定義：加油站距離陣列dis[n+2], 汽油價格陣列pri[n+2], 兩者一一對應，
接著對這兩個陣列初始化，dis[0] = 0; pri[0] = p; // 將出發點的距離 0 和 油價p 放入陣列
dis[n+1] = d1; pri[n+1] = 0; // 終點的距離 d1, 油價 0 放入陣列
將之后輸入的N行資料按照距離從小到大排列，需要注意的是，交換距離的時候需要將對應的價格也交換，
那么只需要從距離最小的點開始出發，依次進行計算，
需要注意的地方：1、每次都需要判斷是否能夠到達下一個加油站，如果無法到達，則直接退出，
2、每次在當前能夠走到的最遠距離內進行判斷，尋找是否有比當前油價更低的加油站，如果沒有更低的，價格相等也可以，
3、由于最后一點 pir[n+1] 的油價為0，所以要對其特殊處理，
四、實作代碼（C語言）
1、帶注釋的代碼，運行也有輸出提示，可以用來糾錯，
#include <stdio.h>
#include <stdbool.h> // 洛谷編譯器識別 bool 型別需要加入這個頭檔案
int main() { float d1, c, d2, p; int n, i, j; scanf("%f %f %f %f %d", &d1, &c, &d2, &p, &n); float pri[n+2]; // 價格 float dis[n+2]; // 距離 float minPri, nowDis=0.0, nowOil=0.0; // 最少價格，當前距離, 當前油量 float maxdis; // 能行駛的最大距離 int min;// 最低價格的下標 bool flag = false,is = false; // 當前是否有最優解, 能否到達， 已經到達 pri[0] = p; // 初始點油價為p dis[0] = 0; // 距離為0 dis[n+1] = d1; // 終點距離為D1 pri[n+1] = 0; // 油價為0 float fpri = 0; // 最終價格 for(i = 1; i <= n; i++) { scanf("%f %f",&dis[i], &pri[i]); } /*將價格和距離的陣列按照 距離出發點的距離從小到大排序*/ for(i = 1; i <= n; i++) { for(j = i; j <= n; j++) { if(dis[i] > dis[j]) { float td = pri[i]; pri[i] = pri[j]; pri[j] = td; p = dis[i]; dis[i] = dis[j]; dis[j] = p; } } } printf("排序結果為：\n價格："); for(i = 0; i <= n+1; i++) { pri[i] = ((int)(100*pri[i] + 0.5))/100.0; printf("%f " ,pri[i]); } printf("\n距離："); for(i = 0; i <= n+1; i++) { dis[i] = ((int)(100*dis[i] + 0.5))/100.0; printf("%f " ,dis[i]); } printf("\n"); i = 0; j = 0; /*排序完成(冒泡排序，時間復雜度On(^2))*/ while(1) { printf("當前位置：%d\n", i); if(i >= n+1) // 已經到達最后一站 { is = true; break; } maxdis = dis[i] + c * d2; if(maxdis < dis[i+1]) // 當前站無法到達下一站 { is = false; break; } flag = false; // 最優標志恢復初始狀態 min = i+1; for(j = i+1; j < n+2; j++) // 從當前油站的下一站開始判斷 { if(maxdis < dis[j]) // 無法到達該位置的加油站，取消判斷 { break; } if(pri[j] <= pri[min] && j < n+1) // 查詢此處加油站的價格是否比當前最低價格更低, 并且此處不是終點 { if(pri[j] != pri[min]) { min = j; } if(pri[j] <= pri[i]) // 此地價格是否等于或低于當前油價并且不是終點 { printf("找到了價格更低的加油站：%d\n", j); flag = true; break; } } } if(flag) // 能找到比當前更低的地方 { fpri += (dis[min] - dis[i] - nowOil*d2) / d2 * pri[i]; // 只加油到能夠到達的那個加油站 i = min; // 到達最低位置的加油站 } else // 找不到更低的 { if(j >= n+2) // 能夠到達終點 { printf("找不到更低的加油站，但可以到達終點!\n"); fpri = fpri + (dis[n+1] - dis[i] - nowOil*d2) / d2 * pri[i]; nowOil = 0; i = j; // 到達終點 } else // 直接加滿 { printf("找不到更低的加油站，也無法到達終點，但找到了最低的加油站位置：%d!\n", min); fpri += (c-nowOil)*pri[i]; nowOil = c - (dis[min] - dis[i]) / d2; i = min; // 到達最低位置的加油站 } } printf("當前位置: %d, 當前消耗金錢 is %f, 剩余油量 is %f\n", i, fpri, nowOil); } if(!is) { printf("No Solution"); } else { fpri = ((int)(100*fpri + 0.5))/100.0; // 實作四舍五入 printf("%.2f", fpri); } return 0; }
2、純代碼，可直接放入NOIP給的編譯器運行
#include <stdio.h> #include <stdbool.h> int main() { float d1, c, d2, p; int n, i, j; scanf("%f %f %f %f %d", &d1, &c, &d2, &p, &n); float pri[n+2]; float dis[n+2]; float nowOil=0.0; float maxdis; int min; bool flag = false,is = false; pri[0] = p; dis[0] = 0; dis[n+1] = d1; pri[n+1] = 0; float fpri = 0; for(i = 1; i <= n; i++) { scanf("%f %f",&dis[i], &pri[i]); } for(i = 1; i <= n; i++) { for(j = i; j <= n; j++) { if(dis[i] > dis[j]) { float td = pri[i]; pri[i] = pri[j]; pri[j] = td; p = dis[i]; dis[i] = dis[j]; dis[j] = p; } } } i = 0; j = 0; while(1) { if(i >= n+1) { is = true; break; } maxdis = dis[i] + c * d2; if(maxdis < dis[i+1]) { is = false; break; } flag = false; min = i+1; for(j = i+1; j < n+2; j++) { if(maxdis < dis[j]) { break; } if(pri[j] <= pri[min] && j < n+1) { if(pri[j] != pri[min]) min = j; if(pri[min] <= pri[i]) { flag = true; break; } } } if(flag) { fpri += (dis[min] - dis[i] - nowOil*d2) / d2 * pri[i]; nowOil += (dis[min] - dis[i]) / d2; nowOil -= (dis[min]-dis[i])/d2; i = min; nowOil -= (dis[min]-dis[i])/d2; i = min; } else { if(j >= n+2) { fpri = fpri + (dis[n+1] - dis[i] - nowOil*d2) / d2 * pri[i]; nowOil += (dis[j] - dis[i]) / d2; i = j; } else { fpri += (c-nowOil)*pri[i]; nowOil = c; nowOil -= (dis[min]-dis[i])/d2; i = min; } } } if(!is) { printf("No Solution"); } else { fpri = ((int)(100*fpri + 0.5))/100.0; printf("%.2f", fpri); } return 0; }
五、完成時間
2021-01-20 15:46:54
零零散散用了近三個小時，快急哭了都，555~~~~~，
下次給思路加上思維導圖吧，不然總覺得稀里糊涂的.........
下面是通過成功截圖（雖然通過了，但也提交了七八次，甚至可能還有問題，請多加注意~~~~~）
六、補充一些輸入與對應的正確輸出
輸入： 87.75 13.03 5.75 7.29 3 22.10 7.38 24.21 6.81 82.08 6.96 輸出： 105.95 粘貼記得去回車和中文字符
輸入： 475.6 11.9 27.4 14.98 6 102.0 9.99 220.0 13.29 256.3 14.79 275.0 10.29 277.6 11.29 381.8 10.09 輸出 192.15
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/251489.html
標籤：其他