C語言源碼： [cpp] #include<stdio.h> #include<stdlib.h> #include<limits.h> #define maxsize 600 double 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; else return -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; else return -1; } void pri(int i,double oil) {//初始值0，0 int j,k; j=find(i);//找離i站距離在一箱油之內的比i站油價低的站 if(j!=-1) {//如果找到了 k=i+1; while(k<=j) if(sta[k].price<sta[i].price) break; else k++;//找距離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; while(scanf("%lf %lf %lf %d",&cmax,&length,&davg,&n)!=EOF) { 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(sta[0].length!=0) printf("The maximum travel distance = 0.00\n"); else if(i<n) { if(sta[0].length==0) printf("The maximum travel distance = %.2lf\n",sta[i].length+lengthcmax); else printf("The maximum travel distance = 0.00\n"); } else { pricemin=0; pri(0,0); printf("%.2lf\n",pricemin); } } return 0; }
