内容简介:这一道题是贪心算法中接触到的比较难的题目,关键是难以归纳出具体的做法步骤,这里详解以下示例给出的步骤:首先,将加油站进行距离排序;
这一道题是贪心算法中接触到的比较难的题目,关键是难以归纳出具体的做法步骤,这里详解以下示例给出的步骤:
首先,将加油站进行距离排序;
示例将选择可到达范围内的下一节点分为了两种情况:
1.如果在可到达范围内第一次出现了低于当前油价的站点,则到达该站点;
这个选择的依据是,如果我们在a,有a->b->c,b站点油价便宜,所以我们应该去b加油再跑到c,而不是加a站的油跑到c。
2.如果第一种情况没有出现,所有可达站点油价都比当前站点贵,则我们应该找到可达站点油价最小的那一个,作为下一站。但是这里有一个非常重要的操作,就是加满油再去;
这个操作的依据是:如果我们在a,有a->b->c,b站点油价比a贵,如果我们从a加满到b,剩下v升油,比没加满从b到c可以省钱,所以应该先在a加满,去b,从而在及进行判断;
整体来说,每到一个站点判断一次,只判断当前站点到下一站点的最优解,从而使得通过贪心算法达到整体最优;
代码如下所示:
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<vector> #include<cmath> #include<algorithm> using namespace std; using std::vector; const int maxn=510; const int INF=10000000000; struct station{ double dis; double price; }st[maxn]; bool cmp(station a,station b){ return a.dis<b.dis; } int main(){ int n; double Cmax,D,Davg; scanf("%lf%lf%lf%d",&Cmax,&D,&Davg,&n); for(int i=0;i<n;i++){ scanf("%lf%lf",&st[i].price,&st[i].dis); } st[n].dis=D; st[n].price=0; sort(st,st+n,cmp); if(st[0].dis!=0){ printf("The maximum travel distance = 0.00\n"); }else{ int now=0;//现在的站点; double ans=0;//总花费 double nowTank=0;//当前油箱余量; double MAX=Cmax*Davg;//最大行走距离; while(now<n){ //先进行最小站点的选择; int next_station=-1; double min_price=INF; for(int i=now+1;i<=n&&st[i].dis-st[now].dis<=MAX;i++){ if(st[i].price<min_price){ min_price=st[i].price; next_station=i; if(st[i].price<st[now].price){ //如果小于当前起点的油价,直接退出 break; } } } //已经获得下一站的目的; if(next_station==-1) break;//没有找到下一站 double need=(st[next_station].dis-st[now].dis)/Davg;//到下一站所需要的油量 if(min_price<st[now].price){ //如果是低于当前节点的中继站 if(nowTank<need){ //如果当前油量不支持到达下一站 ans+=(need-nowTank)*st[now].price; nowTank=0; }else{ nowTank-=need; } }else{ //到了更远的一站; //当前站油便宜,直接拉满 ans+=(Cmax-nowTank)*st[now].price; nowTank=Cmax-need; } now=next_station; } if(now==n){ printf("%.2f\n",ans); }else{ printf("The maximum travel distance = %.2f\n",st[now].dis+MAX); } } system("pause"); return 0; }
以上所述就是小编给大家介绍的《PAT A1033 重点题》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
How Great Decisions Get Made
Maruska, Don / 2006-2 / $ 20.28
All too often, solving tough work issues can become a tug of war as clashing departments, priorities, personality styles, and other concerns threaten to destroy any possibility of a successful conclus......一起来看看 《How Great Decisions Get Made》 这本书的介绍吧!