问题描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空
的) 。给定两个城市之间的距离 D1、汽车油箱的容量 C(以升为单位) 、每升汽油能行驶的
距离 D2、出发点每升汽油价格 P 和沿途油站数 N(N 可以为零) ,油站 i 离出发点的距离
Di、每升汽油价格 Pi(i=1,2, ……N) 。计算结果四舍五入至小数点后两位。如果无法到达
目的地,则输出“No Solution” 。
输入格式
第一行为 4 个实数 D1、C、D2、P 与一个非负整数 N;
接下来 N 行,每行两个实数 Di、Pi。
输出格式
如果可以到达目的地,输出一个实数(四舍五入至小数点后两位) ,表示最小费用;否
则输出“No Solution” (不含引号) 。
样例输入
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
样例输出
26.95
#include <stdio.h> #include <string.h> #define MAX 1000 int main() { float left,sum; float D1,C,D2,P; int N; float dis[MAX],price[MAX]; int i,j; scanf("%f%f%f%f%d",&D1,&C,&D2,&P,&N); for(i=1;i<=N;i++) { scanf("%f%f",&dis[i],&price[i]); } dis[0]= 0; dis[N+1] = D1; price[0] = P; price[N+1] = 0; for(i=1;i<=N+1;i++)/*油箱中的油能否跑完每一站*/ { if(dis[i] - dis[i-1] > C * D2) { printf("No Solution\n"); return 0; } } sum = 0; left = 0; for(i=0;i<=N;i=j) { for(j=i+1;j<=N+1;j++) { if(dis[j]-dis[i] > C * D2) //在C * D2 的距离内N+1个加油站寻找最便宜的加油站 { j--; break; } if( price[j] < price[i]) // 找到更便宜的加油站 break; } if(price[j] < price[i]) //有找到更便宜的加油站 { sum += ((dis[j] -dis[i])/D2 - left) * price[i]; left = 0; } else { sum += (C - left) * price[i];//加满油箱 left = C- (dis[j]-dis[i])/D2 ; } } printf("%.2f\n",sum); return 0; }
by 吴尚奇 Devil_box 2014/06