题目：http://pat.zju.edu.cn/contests/pat-a-practise/1033
题意：如果不能抵达终点，输出最大行驶距离;如果能抵达终点，输出最小邮费。
思路：贪心思想。距离一定，每一段都尽可能使用单价较低的油。假设当前在第tmp个加油站，如果从第tmp+1到第N个加油站间存在第i个加油站的汽油单价小于tmp加油站汽油单价，那么在第tmp个加油站要做的事（加不加油，或加多少）满足所带油刚好能够抵达第i个加油站就好。如果加满都到不了，就加满到下一站(tmp+1)继续考察。
注意：如果距离最近的加油站距离非0，则直接判断无法到达!
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
double price,dis;
}p[511];
bool cmp(node a,node b)
{
return a.dis<b.dis;
}
int main()
{
int Cmax,dis,Davg,n,i;
scanf("%d%d%d%d",&Cmax,&dis,&Davg,&n);
for(i=0;i<n;i++)
scanf("%lf%lf",&p[i].price,&p[i].dis);
sort(p,p+n,cmp);
p[n].dis=dis;
if(p[0].dis>0)
{
printf("The maximum travel distance = 0.00\n");
return 0;
}
double oil=0,sum=0;
int tmp=0;
double maxdis=0;
bool flag=true;
while(true)
{
double remain=(dis-p[tmp].dis)/(double)Davg;
if(remain<=oil) break;
if(Cmax<(p[tmp+1].dis-p[tmp].dis)/(double)Davg)
{
maxdis=p[tmp].dis+(double)Cmax*(double)Davg;
flag=false;
break;
}
bool flagmin=false;
for(i=tmp+1;i<n;i++)
if(p[i].price<p[tmp].price)
{
flagmin=true;
double need=(p[i].dis-p[tmp].dis)/(double)Davg;
if(need<=oil)
{
oil-=need;
tmp=i;
}
else if(need<=Cmax)
{
sum+=(need-oil)*p[tmp].price;
oil=0;
tmp=i;
}
else if(need>Cmax)
{
sum=sum+(Cmax-oil)*p[tmp].price;
oil=Cmax-(p[tmp+1].dis-p[tmp].dis)/(double)Davg;
tmp=tmp+1;
}
break;
}
if(!flagmin)
{
if(remain<=Cmax)
{
sum=sum+(remain-oil)*p[tmp].price;
break;
}
sum=sum+(Cmax-oil)*p[tmp].price;
oil=Cmax-(p[tmp+1].dis-p[tmp].dis)/(double)Davg;
tmp=tmp+1;
}
}
if(flag) printf("%.2f\n",sum);
else printf("The maximum travel distance = %.2f\n",maxdis);
return 0;
}
PAT 1033. To Fill or Not to Fill,布布扣,bubuko.com
PAT 1033. To Fill or Not to Fill
原文：http://blog.csdn.net/zqh_1991/article/details/21182873