2012年第3题
题目地址：http://pat.zju.edu.cn/contests/pat-a-practise/1033
C语言源码：
#include<stdio.h>#include<stdlib.h>#include<limits.h>#define maxsize 600double lengthcmax,pricemin,falg;double cmax,length,davg;int n;typedef struct station{double price;double length;}station;station sta[maxsize];int cmp(const void *a,const void *b){station *aa=(station *)a;station *bb=(station *)b;return aa->length>bb->length?1:-1;}int find(int i){int j,fprice=INT_MAX;double price=INT_MAX;for(j=i+1;j<n&&sta[i].length+lengthcmax>=sta[j].length;j++){if(sta[j].price<price&&sta[j].price<sta[i].price){price=sta[j].price;fprice=j;}}if(fprice<n&&sta[fprice].price<sta[i].price)return fprice;elsereturn -1;}int findmin(int i){int j,fprice=INT_MAX;double price=INT_MAX;for(j=i+1;j<n&&sta[i].length+lengthcmax>=sta[j].length;j++){if(sta[j].price<price){price=sta[j].price;fprice=j;}}if(fprice<n)return fprice;elsereturn -1;}void pri(int i,double oil){//初始值0，0int j,k;j=find(i);//找离i站距离在一箱油之内的比i站油价低的站if(j!=-1){//如果找到了k=i+1;while(k<=j)if(sta[k].price<sta[i].price)break;elsek++;//找距离i最近的比i油价低的站，驶向k站，到k站邮箱清空pricemin+=((sta[k].length-sta[i].length)/davg-oil)*sta[i].price;pri(k,0);}else{//未找到if(sta[i].length+lengthcmax>=sta[n].length)//如果距离终点在一箱油距离之内，直接驶向终点pricemin+=((sta[n].length-sta[i].length)/davg-oil)*sta[i].price;else{j=findmin(i);//找离i站距离在一箱油之内油价最低的站，加满油，驶向j站pricemin+=(cmax-oil)*sta[i].price;pri(j,cmax-(sta[j].length-sta[i].length)/davg);}}}int main(){int i;scanf("%lf %lf %lf %d",&cmax,&length,&davg,&n);lengthcmax=cmax*davg;for(i=0;i<n;i++)scanf("%lf %lf",&sta[i].price,&sta[i].length);qsort(sta,n,sizeof(sta[0]),cmp);sta[n].length=length;sta[n].price=INT_MAX;for(i=0;i<n;i++)if(sta[i].length+lengthcmax<sta[i+1].length)break;if(i<n){if(sta[0].length==0)printf("The maximum travel distance = %.2lf\n",sta[i].length+lengthcmax);elseprintf("The maximum travel distance = 0.00\n");}else{pricemin=0;pri(0,0);printf("%.2lf\n",pricemin);}return 0;}