题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1D1D1、汽车油箱的容量CCC（以升为单位）、每升汽油能行驶的距离D2D2D2、出发点每升汽油价格PPP和沿途油站数NNN（NNN可以为零），油站iii离出发点的距离DiDiDi、每升汽油价格PiPiPi（i=1,2,…,Ni=1,2,…,Ni=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入格式
第一行，D1D1D1，CCC，D2D2D2，PPP，NNN。
接下来有NNN行。
第i+1i+1i+1行，两个数字，油站i离出发点的距离DiDiDi和每升汽油价格PiPiPi。
输出格式
所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入输出样例
输入 #1
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
输出 #1
26.95
说明/提示
N≤6,其余数字≤500
思路：
这是道模拟题，注意情况讨论。
代码：
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<algorithm>
#define N 100000
using namespace std;
double d1,c,d2,p,maxx,mo,len;
int n;
struct node{
double cos,dis;
}e[N];
bool cmp(node a,node b)
{
return a.dis<b.dis;
}
int move(int now)
{
int can=99999;
int f=e[now].dis;
for(int i=now+1;i<=n&&e[i].dis-f<=maxx;i++)
{
if(e[i].cos<e[now].cos)
{
mo+=(e[i].dis-f-len)/d2*e[now].cos;
len=0;
return i;
}
if(can==99999||e[i].cos<e[can].cos)can=i;
}
if(d1-e[now].dis<=maxx)
{
mo+=(d1-e[now].dis-len)/d2*e[now].cos;
return 9999;
}
if(can==99999)
{
puts("No Solution");
return -1;
}
else
{
mo+=c*e[now].cos;
len+=(maxx-e[can].dis+f);
return can;
}
}
int main()
{
scanf("%lf%lf%lf%lf%d",&d1,&c,&d2,&p,&n);
for(int i=1;i<=n;i++)
{
scanf("%lf%lf",&e[i].dis,&e[i].cos);
}
e[0].dis=0;
e[0].cos=p;
sort(e+1,e+n+1,cmp);
maxx=c*d2;
int k=0,t;
do{
t=move(k);
k=t;
if(t==-1)return 0;
}while(t!=9999);
printf("%.2f",mo);
return 0;
}
