題目描述

有了高速公路，開(kāi)車從杭州到任何其他城市都很容易。但由于汽車的油箱容量有限，我們必須不時(shí)地在路上找到加油站。不同的加油站可能會(huì)給出不同的價(jià)格。你被要求仔細(xì)設(shè)計(jì)最便宜的路線去。

輸入描述:

對(duì)于每個(gè)測(cè)試實(shí)例

第一行包含4個(gè)正數(shù)：Cmax（<=100），即油箱的最大容量；D（<=30000），即杭州到目的地城市的距離；Davg（<=20），即汽車每單位汽油可行駛的平均距離；N（<=500），即加油站總數(shù)。

接下來(lái)是N行，每行包含一對(duì)非負(fù)數(shù)：Pi，煤氣單價(jià)，Di（<=D），這個(gè)站到杭州的距離，i=1，…N。一行中的所有數(shù)字用空格隔開(kāi)。

輸出描述:

對(duì)于每個(gè)測(cè)試用例，一行打印最便宜的價(jià)格，精確到小數(shù)點(diǎn)后2位。假設(shè)開(kāi)始時(shí)油箱是空的。如果無(wú)法到達(dá)目的地，請(qǐng)打印“最大行駛距離=X”，其中X是車輛可以行駛的最大可能距離，精確到小數(shù)點(diǎn)后2位。

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

輸出

749.17 The maximum travel distance = 1200.00

思路一：

采用貪心的做法，情況如下：

先對(duì)輸入的加油站進(jìn)行距離升序排序（如果距離相同，按照價(jià)格從小到大，因?yàn)榫嚯x相同的油站我們?nèi)∽畋阋说?#xff09;。

1.剛開(kāi)始，車沒(méi)油，所以要找0距離油價(jià)最少的那一個(gè),如果起始點(diǎn)沒(méi)有油站，那么車無(wú)法走，直接認(rèn)為無(wú)解

2.然后考察車的最大距離(Cmax*Davg)里的所有加油站，看看是否有比當(dāng)前油價(jià)便宜的加油站

?①.若有，此時(shí)若剩余油夠到達(dá)，則不用加油，否則，只需把油加到正好可到達(dá)該加油站（遇到的第一個(gè)油價(jià)更便宜的加油站）即可，因?yàn)橹蟮木嚯x我想用便宜的油價(jià)。

?②.若沒(méi)有，我們只能在最大距離內(nèi)找到當(dāng)前油價(jià)最小的那一個(gè)加油站（此時(shí)郵價(jià)仍是比上次貴的）即可，但是此時(shí)我們要把油加滿（因?yàn)楫?dāng)前油價(jià)便宜！），加滿之后，到指定加油站之后繼續(xù)進(jìn)行考察：再次根據(jù)距離，補(bǔ)充油（注意此時(shí)油箱是有油的，上次油價(jià)便宜）。

注意: 若在最大距離內(nèi)一個(gè)車站都找不到，則結(jié)束了，break，輸出已走的最大距離。

代碼:

#include<iostream> #include<cstdio> #include<algorithm> using namespace std;struct GasStation{double Pi;double Di;bool operator < (const GasStation &a) const{if(Di==a.Di)return Pi<a.Pi;elsereturn Di<a.Di;} };int main() {int Cmax,D,Davg,N;GasStation station[501];while(cin>>Cmax>>D>>Davg>>N){for(int i=0;i<N;i++){cin>>station[i].Pi>>station[i].Di;}station[N].Di=D;station[N].Pi=0.0;sort(station,station+N+1);if(station[0].Di!=0){cout<<"The maximum travel distance = 0.00"<<endl;continue;}GasStation Current_station;Current_station=station[0];int Dmax=Cmax*Davg;double p=0.00;double c=0.00;double d_space;int j=0;bool ifstation;bool ischeap;while(Current_station.Di!=D){ischeap=false;ifstation=false;double min_p=100000.0;for(int i=j+1;i<=N;i++){if(station[i].Di<=Current_station.Di+Dmax){ ifstation=true;if(station[i].Pi<Current_station.Pi){ischeap=true;j=i;d_space=station[i].Di-Current_station.Di;if(c>=(d_space/(Davg*1.0))) //這里乘個(gè)1.0是為了把Davg變成double類型{c-=(d_space/(Davg*1.0));}else{p+=((d_space/(Davg*1.0))-c)*Current_station.Pi;c=0.0;}Current_station=station[i];break;}else {if(station[i].Pi<min_p){j=i;min_p=station[i].Pi;}}}}if(!ifstation){printf("The maximum travel distance = %.2lf\n",Current_station.Di+Dmax);break;}if(!ischeap){d_space=station[j].Di-Current_station.Di;p+=(Cmax-c)*Current_station.Pi;c=Cmax-(d_space/(Davg*1.0));Current_station=station[j];}}if(ifstation)printf("%.2lf\n",p);}return 0; }

思路二（非常巧妙）：

【原理：對(duì)結(jié)果進(jìn)行倒推】

【代碼來(lái)源：牛客網(wǎng)用戶"uever"】

對(duì)輸入的加油站進(jìn)行油價(jià)升序排序。

利用貪心策略,從最便宜的加油站開(kāi)始,每個(gè)加油站加的油最多能走cmax*davg路程。利用一個(gè)30000大小的flag數(shù)組記錄是否有重合區(qū)域

代碼：

/* 核心思路:利用貪心策略,從最便宜的加油站開(kāi)始,每個(gè)加油站加的油最多能走cmax*davg路程. 利用一個(gè)30000大小的flag數(shù)組記錄是否有重合區(qū)域 */ #include<cstdio> #include<algorithm> using namespace std;struct sta{double pi;int di;bool operator < (const sta& b) const{return pi<b.pi;} }a[501];int main(){int cmax, d, davg, n;double sum;while(scanf("%d %d %d %d", &cmax, &d, &davg, &n)!=EOF){for(int i=0; i<n; i++) scanf("%lf %d", &a[i].pi, &a[i].di);sort(a, a+n);//sum = 0;//記錄花費(fèi)int flag[30001]={0}, max = cmax*davg, tmp, cnt;for(int i=0; i<n; i++){tmp = (a[i].di+max<d?max:d-a[i].di); //如果到終點(diǎn)距離<max,只需加上足夠走到終點(diǎn)的油cnt = 0; //記錄有多長(zhǎng)距離需要該加油站的油for(int j=a[i].di; j<a[i].di+tmp; j++){if(flag[j]==0){flag[j] = 1;cnt++;}}sum += cnt/(davg*1.0)*a[i].pi; //加上在該加油站的花銷}//checkint i;for(i=0; i<d; i++){//有的路程沒(méi)有被覆蓋到說(shuō)明走不到這里if(flag[i]==0){printf("The maximum travel distance = %.2lf\n", (double)i);break;}}if(i==d){printf("%.2lf\n",sum);}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的加油站问题【贪心】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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