立志用最少的代碼做最高效的表達

---

PAT甲級最優題解——>傳送門

---

With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.

Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive numbers: C
?max (≤ 100), the maximum capacity of the tank; D (≤30000), the distance between Hangzhou and the destination city; Davg(≤20), the average distance per unit gas that the car can run; and N (≤ 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: P?i, the unit gas price, and Di(≤D), the distance between this station and Hangzhou, for i=1,?,N. All the numbers in a line are separated by a space.

Output Specification:
For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print The maximum travel distance = X where X is the maximum possible distance the car can run, accurate up to 2 decimal places.

Sample Input 1:
50 1300 12 8
6.00 1250
7.00 600
7.00 150
7.10 0
7.20 200
7.50 400
7.30 1000
6.85 300
Sample Output 1:
749.17

Sample Input 2:
50 1300 12 2
7.10 0
7.00 600
Sample Output 2:
The maximum travel distance = 1200.00

---

我們把目的地看做一個油價為0，距離為distance的加油站，放到加油站數組的最后
1.算法的核心思想是，如果在能達到的范圍內有比現在油箱里的油更便宜的加油站
2.那就先加恰好能到那個加油站的油，到達目的加油站之后，再重復1st
3.如果在能抵達的范圍內沒有比油箱里的油更便宜的，就找范圍內最便宜的加油站直接抵達
然后再站在新的站點上考慮里程范圍內，重復1st

---

#include<bits/stdc++.h> using namespace std; struct station{double price;double dis; }sta[505];bool cmp(station a,station b) { return a.dis<b.dis; }int main() {double cmax,distance,davg;int n;cin>>cmax>>distance>>davg>>n;for(int i=0;i<n;i++) cin>>sta[i].price>>sta[i].dis;sta[n].price=0;sta[n].dis=distance;sort(sta,sta+n,cmp);if(sta[0].dis!=0)//出發點沒有加油站，走不了 cout<<"The maximum travel distance = 0.00";else {int now=0;//now是實時站點 double prices=0,nowtank=0;//nowtank是油箱目前油量，prices是總花費 double range=cmax*davg;//續航里程 while(now<n) {//達到目的地站點n之前一直循環 int k=-1;double Min_price=1000000000;for(int i=now+1;i<=n&&sta[i].dis-sta[now].dis<=range;i++) { //在續航里程內檢索加油站 if(sta[i].price<Min_price) { //尋找里程內油價最低的加油站 Min_price=sta[i].price;k=i;if(Min_price<sta[now].price)//找到比當前加油站更便宜的加油站，立即退出循環，前往該加油站 break; }}if(k==-1) break;//沒有符合條件的加油站，退出循環 double need=(sta[k].dis-sta[now].dis)/davg; if(Min_price<sta[now].price) { //里程范圍里有比現在加油站便宜的油，直接進到目的地 if(nowtank<need) { //如果油箱的油不夠達到目的地，補上恰好能到目的地的油 prices+=(need-nowtank)*sta[now].price;nowtank=0;}else nowtank-=need; //油箱的油足夠到達目的地 }else {//接下來里程內沒有比現在便宜的加油站，在當前的加油站把油箱加滿(先加滿最便宜的油) prices+=(cmax-nowtank)*sta[now].price;nowtank=cmax-need;}now=k;//更新到目的地加油站 }if(now==n) printf("%.2f",prices);//沒有到達目的地，輸出能達到的最大距離，即現在所在加油站和出發點的距離，和續航里程range else printf("The maximum travel distance = %.2f",sta[now].dis+range);}return 0; }

---

耗時：

總結

以上是生活随笔為你收集整理的【详细解析】1033 To Fill or Not to Fill (25 分)的全部內容，希望文章能夠幫你解決所遇到的問題。

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