https://pintia.cn/problem-sets/994805342720868352/problems/994805458722734080

#include<cstdio> #include<algorithm> using namespace std; struct gas {double price;double km; }g[520]; bool cmp(gas a,gas b)//距離由小到大排 {return a.km<b.km; } int main(void) {double max_oil;//最大的油量 double km;//距離 double speed;//速度int n;//油箱的數(shù)目int i;//循環(huán)變量 double maxkm=0; //滿油的最遠距離bool flag=true; //判斷可不可以到達 double x=0;//不可到達的，最遠距離 scanf("%lf%lf%lf%d",&max_oil,&km,&speed,&n); maxkm=max_oil*speed;//滿油的最遠距離 for(i=0;i<n;i++){scanf("%lf%lf",&g[i].price,&g[i].km);}//哨兵 g[n].price = 0;//數(shù)組最后面放置終點，價格為0g[n].km = km;//終點距離為kmsort(g,g+n,cmp);//按距離從小到大排序 if(g[0].km!=0)//原點沒有加油站 {flag=false;printf("The maximum travel distance = 0.00\n");return 0;}else//原點有加油站判斷可不可以到達 { for(i=1;i<n;i++){if(maxkm< (g[i].km-g[i-1].km) )//我的最遠距離不能到達下一個加油站。 {x=g[i-1].km+maxkm;flag=false;break;}x=g[i].km;}if(i==n)//說明我可以到最后一個加油站。 {if(maxkm < ( km-g[n-1].km) ){//最后一個加油站到終點的距離大于我的最大行駛距離 flag=false;x=g[n-1].km+maxkm;}} }if(flag){int now=0;//當(dāng)前所在的加油站編號 初始為0double now_oil=0;//現(xiàn)在的油量double money=0;//總的金錢。 while(now<n){int minPrice_index=-1;//最便宜的油的編號double minPrice=100000;for(i=now+1;i<=n&&(g[i].km-g[now].km)<=maxkm;i++)//找到可以到達的加油站數(shù)目 {if(g[i].price<minPrice)//下一個站的油比我標(biāo)記的最低油價的低 {minPrice=g[i].price;//保存 minPrice_index=i;if(minPrice<g[now].price)//如果找到第一個比當(dāng)前便宜的站 break;}}double need=(g[minPrice_index].km-g[now].km)/speed;if (minPrice < g[now].price)//如果最低加油站的油價,低于當(dāng)前油價{money += (need - now_oil)*g[now].price;//補足neednow_oil = 0;//到達加油站minPrice_index后油箱內(nèi)油量為0 }else//如果加油站minPrice_index的油價高于當(dāng)前油價{money += (max_oil - now_oil)*g[now].price;//將油箱加滿//到達加油站k后油箱內(nèi)油量為Cmax-neednow_oil = max_oil - need;}now = minPrice_index;//到達加油站minPrice_index，進入下一層循環(huán)}printf("%.2lf\n",money);}elseprintf("The maximum travel distance = %.2lf\n",x);return 0; }

總結(jié)

以上是生活随笔為你收集整理的1033 To Fill or Not to Fill (25 分)【难度: 难 / 知识点: 模拟 贪心】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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