本文主要是介绍pat-advanced-1033，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1033. To Fill or Not to Fill (25)
With highways available, driving a car from Hangzhou to any other city is easy. But since the tank capacity of a car is limited, we have to find gas stations on the way from time to time. Different gas station may give different price. You are asked to carefully design the cheapest route to go.
Input Specification:
Each input file contains one test case. For each case, the first line contains 4 positive numbers: Cmax (<= 100), the maximum capacity of the tank; D (<=30000), the distance between Hangzhou and the destination city; Davg (<=20), the average distance per unit gas that the car can run; and N (<= 500), the total number of gas stations. Then N lines follow, each contains a pair of non-negative numbers: Pi, the unit gas price, and Di (<=D), the distance between this station and Hangzhou, for i=1,...N. All the numbers in a line are separated by a space.
Output Specification:
For each test case, print the cheapest price in a line, accurate up to 2 decimal places. It is assumed that the tank is empty at the beginning. If it is impossible to reach the destination, print "The maximum travel distance = X" where X is the maximum possible distance the car can run, accurate up to 2 decimal places.
Sample Input 1:50 1300 12 8 6.00 1250 7.00 600 7.00 150 7.10 0 7.20 200 7.50 400 7.30 1000 6.85 300Sample Output 1:
749.17Sample Input 2:
50 1300 12 2 7.10 0 7.00 600Sample Output 2:
The maximum travel distance = 1200.00
思路：
1.若起点无加油站，则不能出发（注意距离也要用浮点数表示，注意eps的使用）
2.若可以出发，则从该点开始查找在可达范围内的价格最低的加油站（在我看别人的解题思路时，一个分层油箱的概念挺有意思的，即油箱中有不同价格的油，但是使用时优先使用最便宜的油，可以用优先队列实现）
3.价格最低的加油站分为两种：（1）价格小于当前加油站并且是价格小于当前加油站中的离当前位置最近的 （2）价格大于当前加油站的它是当前加油站可达范围内最便宜的
4.根据这两种情况确定贪心策略：（1）首先在起点把油箱装满 （2）对于第一种加油站一旦遇到就先把剩余的油抛弃掉再把油箱装满 （3）对于第二种加油站，把油箱装满但不要把以前更便宜的油扔掉
5.当到达下一个点时，才计算上一个点的消耗，可以把终点当做一个价格为0加油站放入数组中，需要对数组排序
#include<stdio.h>
#include<algorithm>
#include<math.h>
#include<queue>
#define eps 1e-8
using namespace std;
struct list
{double price;double pos;
};
struct petrol
{double vol;double price;petrol() { }petrol(double c,double d){vol=c;price=d;}friend bool operator < (struct petrol a,struct petrol b){return a.price>b.price;}
};
bool cmp(struct list a,struct list b)
{if(fabs(a.pos-b.pos)<=eps)return a.price<b.price;elsereturn a.pos<b.pos;
}
int main()
{double c,d,p,maxd;int n;struct list an[505];scanf("%lf%lf%lf%d",&c,&d,&p,&n);for(int i=0;i<n;i++){scanf("%lf%lf",&an[i].price,&an[i].pos);}an[n].price=0;an[n].pos=d;sort(an,an+n+1,cmp);if(an[0].pos!=0)printf("The maximum travel distance = 0.00");else{double res=0,dis=0,remain=0;int gs=0;priority_queue<struct petrol> q;maxd=c*p;q.push(petrol(c,an[gs].price));remain=c;while(fabs(d-dis)>=eps){int flag=1,mini=gs;double min=10000000,sub,cost;for(int i=gs+1;an[i].pos-an[gs].pos<=maxd&&i<=n;i++){if(an[gs].price>an[i].price){sub=an[i].pos-an[gs].pos; cost=sub/p;while(!q.empty()&&cost!=0){if(q.top().vol>cost){res+=cost*q.top().price;q.pop();cost=0;}else{remain-=q.top().vol;cost-=q.top().vol;res+=q.top().vol*q.top().price;q.pop();}}while(!q.empty()&&cost!=0)q.pop();q.push(petrol(c,an[i].price));dis+=sub;remain=c;gs=i;flag=0;break;}else if(an[gs].price<=an[i].price&&an[i].price<min){min=an[i].price;mini=i;}}if(mini==gs){while(!q.empty()){dis+=q.top().vol*p;q.pop();}break;}if(flag){sub=an[mini].pos-an[gs].pos;cost=sub/p;while(!q.empty()&&cost!=0){if(q.top().vol>cost){struct petrol Q=q.top();remain-=cost;Q.vol-=cost;res+=cost*q.top().price;q.pop();q.push(Q); cost=0;}else{remain-=q.top().vol;cost-=q.top().vol;res+=q.top().vol*q.top().price;q.pop();}}q.push(petrol(c-remain,an[mini].price));remain=c;dis+=sub;gs=mini;} }if(dis==d)printf("%.2f",res);elseprintf("The maximum travel distance = %.2f",dis);}return 0;
}
这篇关于pat-advanced-1033的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
