一个题折磨了我三个小时。。。
思路:
贪心:
1.起步时,如果没有距离是0的加油站,肯定走不了
2.在每个加油站都判断在最大油箱行驶距离内是否有比当前油价更便宜的
2.1如果没有,则加满(如果能直接到终点就加到终点的油就行了,这样比较便宜)。并且判断是否两个加油站的距离大于油箱的最大行驶距离,如果是直接输出;如果不是继续循环。
2.2如果有,则加到那个加油站的油就行了。
#include<iostream> #include<math.h> #include<vector> #include<algorithm> using namespace std; double Cmax,D,Davg,N,dis,price,gomax,ans,cur;//gomax为油加满的最大行驶距离。ans为最后的输出 。cur为当前的油量 struct station{ double p; double d; station(double pp,double dd):p(pp),d(dd){} inline bool operator <(const station &s)const{ return d<s.d; } };vector<station> vec; int main(){ while(cin>>Cmax>>D>>Davg>>N){ vec.clear(); bool ret=false; gomax=Cmax*Davg;ans=0,cur=0; for(int i=0;i<N;i++){ cin>>price>>dis; vec.push_back(station(price,dis)); }sort(vec.begin(),vec.end());//按距离进行排序 if(vec[0].d!=0){ printf("The maximum travel distance = 0.00\n"); ret=true; }else{ for(int i=0;i<vec.size();i++){ if(i==vec.size()-1){//判断当前油能不能到终点,如果能就break;如果不能则要加一点油。 double needdis=D-vec[i].d; if(needdis<=gomax){ //能到终点 if(cur<needdis/Davg){ ans+=(needdis/Davg-cur)*vec[i].p; } }else{ printf("The maximum travel distance = %.2f\n",vec[i].d+gomax); ret=true; }break; } double min=vec[i].p;int index=i; if(vec[i+1].d-vec[i].d>gomax){//后一个加油站的距离大于油箱的最大行驶距离。 printf("The maximum travel distance = %.2f\n",vec[i].d+gomax); ret=true; break; } for(int j=i+1;j<vec.size();j++){ if(vec[j].d-vec[i].d<=gomax){ if(vec[j].p<min){ index=j;//找到了最近的一个比当前加油站便宜的加油站,加油加到此地就可以了。 break; } }else break; } if(index==i){//说明油箱最大行驶范围内就当前的加油站最便宜-->加满 if((D-vec[i].d)<=gomax){//如果终点就在眼前,加到终点就可以。 if(cur<(D-vec[i].d)/Davg){ ans+=((D-vec[i].d)/Davg-cur)*vec[i].p; }break; } ans+=(Cmax-cur)*vec[i].p; cur=Cmax-(vec[i+1].d-vec[i].d)/Davg; }else{ double costoil=(vec[index].d-vec[i].d)/Davg; //行驶这段距离需要的油 if(costoil<=cur){//如果需要的油小于还剩的油,不用花钱。 cur-=costoil; }else{ double needoil=costoil-cur; ans+=needoil*vec[i].p; cur=0; } i+=(index-i-1);//-1是因为i还要自加1一次; } } } if(!ret)printf("%.2f\n",ans); } return 0; }