題目描述
一個旅行家想駕駛汽車以最少的費用從一個城市到另一個城市（假設出發時油箱是空的），給定兩個城市之間的距離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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/155880.html
標籤：其他
上一篇：P1015 回文數