題目描寫敘述：

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.

輸入：

For each case, the first line contains 4 positive numbers: Cmax (<= 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: Pi, 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.

輸出：

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.

例子輸入：

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 50 1300 12 2 7.10 0 7.00 600

例子輸出：

749.17 The maximum travel distance = 1200.00

來源：

2012年浙江大學(xué)計(jì)算機(jī)及軟件project研究生機(jī)試真題

這道題確實(shí)挺難的，花了好久的時(shí)間，然后自己考慮不全面，最后參考別人的代碼才搞定。

就不敢寫原創(chuàng)了。。。

http://ziliao1.com/Article/Show/73A96AF77079A6C32C4AA82604FCF691

典型的貪心法。

思想就是考慮下一次在何網(wǎng)站加油（從而決定了在本網(wǎng)站須要加多少油）。

考慮這樣幾種情況：

?????1、到達(dá)下一網(wǎng)站所需油量?>?油箱最大容量：則下一網(wǎng)站不可達(dá)。做法是把油箱加滿，盡可能跑，然后break掉。

?????2、下一網(wǎng)站可達(dá)，且油價(jià)比本網(wǎng)站廉價(jià)：則應(yīng)盡早“換用”更廉價(jià)的油。做法是本站加夠就可以。使得剛好能到達(dá)下一站。

?????3、下一網(wǎng)站可達(dá)。但油價(jià)比本網(wǎng)站貴：此處第一次做錯(cuò)了，不應(yīng)該在本站把油箱加滿，而應(yīng)該繼續(xù)尋找滿油的條件下可達(dá)的下一個(gè)比本站廉價(jià)的網(wǎng)站。若找到，則加夠就可以（所以情況2能夠并到這里）；若未找到，則在本站將油箱加滿。

#include <algorithm>#include <iomanip> #include <iostream> using namespace std; struct station { float price; float dist; }; station st[501]; float cmax, d, davg; int n; bool cmp(station a, station b) { return a.dist < b.dist; } // 尋找下一個(gè)可達(dá)的廉價(jià)網(wǎng)站 int nextCheaper(int now) { for(int i = now; i < n; i++) { if(st[i].dist - st[now].dist > cmax * davg) break; if(st[i].price < st[now].price) return i; } return -1; } int main() { while(cin >> cmax) { cin >> d >> davg >> n; for(int i = 0; i < n; i++) cin >> st[i].price >> st[i].dist; st[n].price = -1; st[n].dist = d; n = n + 1; sort(st, st + n, cmp); int nowst = 0; float nowgas = 0; float cost = 0; while(nowst < n - 1) { if(nowst == 0 && st[0].dist != 0) { st[nowst].dist = 0; break; } float needgas = (st[nowst + 1].dist - st[nowst].dist) / davg; if(needgas > cmax) { float addgas = cmax - nowgas; cost += addgas * st[nowst].price; st[nowst].dist += cmax * davg; break; } int nextc = nextCheaper(nowst); if(nextc == -1) { float addgas = cmax - nowgas; nowgas = cmax; cost += addgas * st[nowst].price; nowgas -= needgas; nowst = nowst + 1; }else{ needgas = (st[nextc].dist - st[nowst].dist) / davg; float addgas = needgas - nowgas; if(addgas > 0) { nowgas += addgas; cost += addgas * st[nowst].price; } nowgas -= needgas; nowst = nextc; } } if(nowst == n - 1) cout << fixed << setprecision(2) << cost << endl; else{ float maxdist = st[nowst].dist; cout << "The maximum travel distance = "<< fixed << setprecision(2) << maxdist << endl; } } return 0; }
以下是我模仿大神自己手寫的代碼，差點(diǎn)兒都改動(dòng)的全然一樣了。。。眼下還是過不了。郁悶

有時(shí)間再研究一下啦。。。如今 真的發(fā)現(xiàn)不了什么錯(cuò)誤了

#include <iostream> #include <cstdio> #include <algorithm> using namespace std; struct station {float pri;float dis; }a[999]; int c,d,davg,n; int cmp(station t1,station t2) {return t1.dis<t2.dis; } int next(int now) {for(int i=now+1;i<=n&&a[i].dis-a[now].dis<=c*davg;i++){if(a[i].pri<a[now].pri)return i;}return -1; }int main() {int i;while(cin>>c>>d>>davg>>n){for(i=0;i<n;i++){scanf("%f %f",&a[i].pri,&a[i].dis);}a[n].pri=-1;a[n].dis=d;sort(a,a+n,cmp);// for(i=0;i<n;i++)//printf("%f %f\n",a[i].dis,a[i].pri);int nowst=0;float anspri=0,ansdis=0,nowgas=0;while(nowst<n){if(nowst==0&&a[0].dis!=0){ansdis=0;break;}float needgas=(a[nowst+1].dis-a[nowst].dis)/davg;if(needgas>c){ansdis+=davg*c;break;}int nextst=next(nowst);// printf("%d %d %f\n",nowst,nextst,anspri);if(nextst==-1){anspri+=(c-nowgas)*a[nowst].pri;nowgas=c-needgas;ansdis=a[nowst+1].dis;nowst+=1;}else{float addgas=(a[nextst].dis-a[nowst].dis)/davg-nowgas;if(addgas>0){nowgas=0;anspri+=addgas*a[nowst].pri;}elsenowgas-=needgas;nowst=nextst;ansdis=a[nowst].dis;}}if(nowst==n)printf("%.2f\n",anspri);elseprintf("The maximum travel distance = %.2f\n",ansdis);}return 0; }/**************************************************************Problem: 1437User: HCA1101Language: C++Result: Wrong Answer ****************************************************************/

轉(zhuǎn)載于:https://www.cnblogs.com/gcczhongduan/p/5266838.html

總結(jié)

以上是生活随笔為你收集整理的九度OJ #1437 To Fill or Not to Fil的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。