题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市(假设出发时油箱是空的)。给定两个城市之间的距离D1D1、汽车油箱的容量CC(以升为单位)、每升汽油能行驶的距离D2D2、出发点每升汽油价格PP和沿途油站数NN(NN可以为零),油站ii离出发点的距离DiDi、每升汽油价格PiPi(i=1,2,…,Ni=1,2,…,N)。计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution”。
输入格式
第一行,D1D1,CC,D2D2,PP,NN。
接下来有NN行。
第i+1i+1行,两个数字,油站i离出发点的距离DiDi和每升汽油价格PiPi。
输出格式
所需最小费用,计算结果四舍五入至小数点后两位。如果无法到达目的地,则输出“No Solution”。
输入输出样例
输入 #1复制
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
输出 #1复制
26.95
说明/提示
N \le 6N≤6,其余数字\le 500≤500
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
double d1,c,d2,p1,ans,now,s,cost;
double d[8],p[8];
bool b;
int main()
{
scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p1,&n);
if(n==0)
{
if(1.0*d1/d2>c)
{
printf("No Solution");
return 0;
}
else
{
ans=1.0*d1/d2*p1;
printf("%.2lf",ans);
return 0;
}
}
for(int i=1;i<=n;++i)
{
scanf("%lf%lf",&d[i],&p[i]);
if(d[i]>d1) d[i]=d1;
if(i==n&&d[i]<d1)
b=1;
}
if(1.0*d[1]/d2<c)
ans+=1.0*d[1]/d2*p1*1.0;
else
{
printf("No Solution");
return 0;
}
cost=p1;
now=1.0*d[1]/d2;
if(b)
{
n++;
d[n]=d1;
// p[n]=p[n-1];
}
int i=2;
while(i<=n)
{
s=d[i]-d[i-1];
if(cost<p[i-1])
{
if(1.0*s/d2<c-now)
{
ans+=1.0*s/d2*cost*1.0;
now+=1.0*s/d2;
}
else
{
ans+=(c-now)*cost*1.0;
d[i-1]=d[i-1]+(c-now)*d2*1.0;
cost=p[i-1];
now=0;
i--;
}
}
else
{
cost=p[i-1];
if(1.0*s/d2<=c)
ans+=1.0*s/d2*cost*1.0;
else
{
printf("No Solution");
return 0;
}
now=1.0*s/d2;
}
i++;
}
printf("%.2lf",ans);
return 0;
}