A1033

没考虑到的点：
1、在没有更低油价的加油站时，前往油价尽可能低的加油站
2、当没有距杭距离为0的加油站时特判输出最远距离

//没能解决的问题： 
//1、now_Price，consumeGap_Total没有处理好，只能适用于某些情况. 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct node{double singlePrice;double hangzhouD;double consumeGap;
}station[510];
bool cmp(node a,node b){return a.hangzhouD<b.hangzhouD;
}
int main(){#ifdef ONLINE_JUDGE#elsefreopen("1.txt","r",stdin);#endifint n;double totalC,totalD,aveD,now_Price=0,now_Distance=0,now_GapC=0,consumeGap_Total=0;scanf("%lf%lf%lf%d",&totalC,&totalD,&aveD,&n);for(int i=0;i<n;i++){                                           //输入 scanf("%lf%lf",&station[i].singlePrice,&station[i].hangzhouD);}sort(station,station+n,cmp);                                    //加油站离杭距离排序 if(station[0].hangzhouD!=0){printf("The maximum travel distance = 0.00");return 0;	}station[n].hangzhouD=totalD;for(int i=0;i<n;i++){                                         //获取各区间耗油量 station[i].consumeGap=(station[i+1].hangzhouD-station[i].hangzhouD)/aveD;}int j=0;for(int i=0;i<n;i++){if(i==j){now_GapC=consumeGap_Total;consumeGap_Total+=station[i].consumeGap;if(station[i].consumeGap>totalC){now_Distance+=totalC*aveD;printf("The maximum travel distance = %.2f",now_Distance);break;}for(j=i+1;j<n&&station[j].singlePrice>station[i].singlePrice;j++){consumeGap_Total+=station[j].consumeGap;if(consumeGap_Total>=totalC){consumeGap_Total=totalC;break;}}now_GapC=consumeGap_Total-now_GapC;}else{now_GapC=0;}now_Price+=now_GapC*station[i].singlePrice;now_Distance+=station[i+1].hangzhouD-station[i].hangzhouD;consumeGap_Total-=station[i].consumeGap;}if(now_Distance>=totalD)printf("%.2f",now_Price);return 0;
}

对着算法笔记敲了一通：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=510;
const int INF=1000000000;
struct station{double price,dis;                //价格、与起点的距离 
}st[maxn];
bool cmp(station a,station b){return a.dis<b.dis; 
}
int main(){#ifdef ONLINE_JUDGE#elsefreopen("1.txt","r",stdin);#endifint 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].price=0;									  //数组最后面放置终点，价格为0st[n].dis=D;									  //终点距离为Dsort(st,st+n,cmp);if(st[0].dis!=0){								  //如果排序后的第一个加油站距离不是0，说明无法前进 printf("The maximum travel distance = 0.00\n");}else{int now=0;									  //当前所处的加油站编号//总花费、当前油量及满油行驶距离double ans=0,nowTank=0,MAX=Cmax*Davg;while(now<n){						 		  //每次循环将选出下一个需要到达的加油站 //选出从当前加油站满油能到达范围内的第一个油价低于当前油价的加油站//如果没有低于当前油价的加油站，则选择价格最低的那个int k=-1;                       		  //最低油价的加油站的编号 double priceMin=INF;            		  //最低油价for(int i=now+1;i<=n&&st[i].dis-st[now].dis<=MAX;i++){if(st[i].price<priceMin){             //如果油价比当前最低油价低 priceMin=st[i].price;             //更新最低油价 k=i;//如果找到第一个油价低于当前油价的加油站，直接中断循环 if(priceMin<st[now].price){break;}}} if(k==-1)break;							  //满油状态下无法找到加油站，退出循环输出结果//下面为能找到可到达的加油站k，计算转移花费//need为从now到k需要的油量double need=(st[k].dis-st[now].dis)/Davg;if(priceMin<st[now].price){               //如果加油站k的油价低于当前油价 //只买足够到达加油站k的油if(nowTank<need){ans+=(need-nowTank)*st[now].price;//补足neednowTank=0;                        //到达加油站k后邮箱内油量为0 }else{								  //如果当前油量超过need nowTank-=need;					  //直接到达加油站k } }else{									  //如果加油站k的油价高于当前油价 ans+=(Cmax-nowTank)*st[now].price;    //将邮箱加满//到达加油站k后邮箱内油量为Cmax-neednowTank=Cmax-need; }now=k; }if(now==n){printf("%.2f\n",ans);}else{printf("The maximum travel distance = %.2f\n",st[now].dis+MAX);}}return 0;
}

自己敲了一下：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=510;
const double INF=1000000000.0;
struct station{double price,dis;
}st[maxn];
bool cmp(station a,station b){return a.dis<b.dis;
}
int main(){#ifdef ONLINE_JUDGE#elsefreopen("1.txt","r",stdin);#endifint 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);}sort(st,st+n,cmp);st[n].price=0;st[n].dis=D;int stNow=0;double Dmax=Cmax*Davg,totalPrice=0,nowTank=0;if(st[0].dis!=0){printf("The maximum travel distance = 0.00\n");return 0;}while(stNow<n){int k=-1;double price_min=INF;for(int i=stNow+1;i<=n&&st[i].dis-st[stNow].dis<=Dmax;i++){if(st[i].price<price_min){price_min=st[i].price;k=i;if(st[i].price<st[stNow].price){break;}}}if(k==-1)break;double need=(st[k].dis-st[stNow].dis)/Davg;if(st[k].price<st[stNow].price){if(nowTank<need){totalPrice+=(need-nowTank)*st[stNow].price;nowTank=0;}else{nowTank-=need;}}else{totalPrice+=(Cmax-nowTank)*st[stNow].price;nowTank=Cmax-need;}stNow=k;}if(stNow==n){printf("%.2f\n",totalPrice);}else{printf("The maximum travel distance = %.2f\n",Dmax+st[stNow].dis);}return 0;
}

第二天写，两处地方没考虑到：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn=510;
const double INF=1000000000; 
struct station{double dis,price;
}stu[maxn];
bool cmp(station a,station b){return a.dis<b.dis;
}
int main(){#ifdef ONLINE_JUDGE#elsefreopen("1.txt","r",stdin);#endifdouble Cmax,D,Davg,total=0,Cbegin=0;int n;scanf("%lf%lf%lf%d",&Cmax,&D,&Davg,&n);for(int i=0;i<n;i++){scanf("%lf%lf",&stu[i].price,&stu[i].dis);}sort(stu,stu+n,cmp);if(stu[0].dis!=0){                                                 //当第一个加油站距杭不是0时，需特判，遗漏了 printf("The maximum travel distance = 0.00\n");return 0;}stu[n].dis=D;stu[n].price=0;int now=0;double MAX=Cmax*Davg;while(now<n){int k=-1;double priceMin=INF;for(int i=now+1;i<=n&&stu[i].dis-stu[now].dis<=MAX;i++){if(stu[i].price<priceMin){priceMin=stu[i].price;k=i;if(priceMin<stu[now].price){break;}}}if(k==-1)break;double need=(stu[k].dis-stu[now].dis)/Davg;if(priceMin<stu[now].price){                                          if(Cbegin<need){									//需判断need,Cbegin哪个更大,开始时遗漏了 total+=(need-Cbegin)*stu[now].price;Cbegin=0;}else{Cbegin-=need;}}else{total+=(Cmax-Cbegin)*stu[now].price;Cbegin=Cmax-need;}now=k;}if(now!=n){printf("The maximum travel distance = %.2f\n",MAX+stu[now].dis);}else{printf("%.2f\n",total);}return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！