首页 > 代码库 > PAT 1033. To Fill or Not to Fill (25)(贪心)
PAT 1033. To Fill or Not to Fill (25)(贪心)
解题思路:
其实题目本身不难,难就难在对贪心策略的选取
在每一个加油点应该做这样的判断:
1、首先计算从本加油点做多可能达到的加油点
2、如果有可达加油点的话:
2.1 寻找有无比当前加油点油价便宜的加油点,如果有的话就跑到该便宜的加油点,油量加到支持到该加油点即可
2.2 如果没有比当前加油点更便宜的加油点的话,又分两种情况:
2.2.1、如果本次加油可能直接到终点,就加可以到达终点的油量
2.2.2、否则的话,加满
3、如果没有可达加油点的话:
3.1 看是否可以直接达到终点
3.2 不能达到终点计算最大抵达路程
warning:这里可能没有第0号加油站哦
代码如下:
#include<iostream> #include<fstream> #include<vector> #include<algorithm> #include<stdio.h> using namespace std; struct station{ double distance; double price; }; vector<station>stations;//加油站信息 double minPrice = 99999999;// 最小的价格 double maxArrived = 0;//最大能够抵达的距离 int cmax,d,davg,n; bool cmp(const station &s1 ,const station &s2){ if(s1.distance>s2.distance)return false ; else return true; } /** @parm currTotalPrice //当前消费 @parm curr 当前位置 @parm gas 当前剩余油量 */ void find_next_station(double currTotalPrice,int curr,double gasLength,double max_len){ vector<int>sindex; double currLen = (stations[curr]).distance; int currIndex = curr; double cheapPrice =9999999; int cheapIndex=0; bool flag = false; for(int i=curr+1;i<stations.size();++i){ if(!flag&&stations[i].distance-currLen <= max_len ){ sindex.push_back(i); if(stations[i].price<stations[curr].price){ cheapPrice = stations[i].price; cheapIndex = i; flag=true; } } } if(sindex.size()>0){ if(cheapPrice<stations[curr].price){//下一个最便宜的比当前的便宜 double pushGasLen = stations[cheapIndex].distance - stations[curr].distance-gasLength; currTotalPrice+=stations[curr].price * pushGasLen*1.0/(davg*1.0) ; gasLength+= pushGasLen; }else{ //下一个加油站没有比当前便宜的了 /** 如果本次可以加油到终点,那就直接加到终点的油量 否则的话直接加满 */ if(stations[curr].distance+max_len>=d){ double pushGasLen = d - stations[curr].distance -gasLength; currTotalPrice += stations[curr].price * pushGasLen*1.0/(davg*1.0); if(currTotalPrice < minPrice){ minPrice=currTotalPrice; } maxArrived = d; return ; }else{ double pushGasLen = max_len - gasLength; currTotalPrice+=stations[curr].price * pushGasLen*1.0/(1.0*davg); gasLength = max_len; } } if(cheapIndex!=0) curr = cheapIndex; else curr = sindex.at(sindex.size()-1); gasLength -= stations[curr].distance-stations[currIndex].distance; find_next_station(currTotalPrice,curr,gasLength,max_len); }else{ /** 即使加满了也不能或者没有下一个加油站了 1、直接抵达终点 2、永远抵达不了终点了 */ if(stations[curr].distance+max_len>=d){//可达 double lastDistance = d-stations[curr].distance; currTotalPrice =currTotalPrice+ (lastDistance*1.0/davg)*stations[curr].price; if(currTotalPrice<minPrice) minPrice = currTotalPrice; maxArrived = d; // cout<<"minPrice "<<minPrice<<endl; }else{//不可达 double distance = stations[curr].distance+max_len; if(distance>maxArrived){ maxArrived = distance; } } return ; } } int main(){ ifstream cin("data.txt"); cin>>cmax>>d>>davg>>n; const double MAX_LEN=cmax*davg; bool noway =true; for(int i=0;i<n;++i){ station s; cin>>s.price>>s.distance; stations.push_back(s); if(s.distance==0){ noway=false; } } if(noway)//没有第0个加油站,汽车启动不了啊 { printf("The maximum travel distance = %.2lf\n",maxArrived); return 0; } sort(stations.begin(),stations.end(),cmp); find_next_station(0,0,0,MAX_LEN); if(maxArrived<d){ printf("The maximum travel distance = %.2lf\n",maxArrived); }else{ printf("%.2lf\n",minPrice); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。