一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱时空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途加油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……，N）。
计算结果四舍五入至小数点后两位。
如果无法到达目的地，则输出“No Solution”。
样例：
Input
D1=275.6 C=11.9 D2=27.4 P=2.8 N=2
|
油站号I
|
离出发点的距离Di
|
每升汽油价格Pi
|
|
1
|
102.0
|
2.9
|
|
2
|
220.0
|
2.2
|
Output
26.95（该数据表示最小费用）
代码：
 #include <iostream>
int main()
 {
 double rest=0,need,p[12],s,c,t,d[12];
int n;
scanf("%lf%lf%lf%lf%d",&s,&c,&t,&p[0],&n);
for(int i=1;i<=n;i++)
scanf("%lf%lf",&d[i],&p[i]);
d[0]=0;
d[n+1]=s;
int k=0,j=0,min=0,min2=0,back=0;
double cost=0;
while(k<=n)
  {
j=k;
while(d[j+1]-d[k]<=c*t&&j<=n)
{
j++;
if(min==0&&p[j]<p[k]) min=j;
if(min2==0||p[j]<p[min2]) min2=j;
 }
if(j==k)
{
printf("No Solution\n");
return 0;
}
if(!min)
{
need=c-rest;
cost+=need*p[k];
rest=c-(d[min2]-d[k])/t;
k=min2;
}
else
 {
need=(d[min]-d[k])/t-rest;
if(need<0)
need=0;
cost+=need*p[k];
rest=0;
k=min;
}
min=min2=0;
}
printf("%.2lf\n",cost);
return 0;
 }
|