题目描述
一个旅行家想驾驶汽车以最小的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离
S
S
S、汽车油箱的容量
C
C
C（以升为单位）、每升汽油能行驶的距离
L
L
L、出发点每升汽油价格
P
0
P_0
P0 和沿途油站数
N
N
N，油站
i
i
i 离出发点的距离
D
i
D_i
Di、油站
i
i
i 每升汽油价格
P
i
(
i
=
1
,
2
,
…
,
N
)
P_i\\ (i=1,2,\\dots,N)
Pi (i=1,2,…,N)，你需要求出最小的费用。
输入格式
第一行，四个实数
S
,
C
,
L
,
P
0
S,C,L,P_0
S,C,L,P0 和一个整数
N
N
N，含义见题目描述。
接下来
N
N
N 行，第
i
+
1
i+1
i+1 行两个实数
D
i
D_i
Di 和
P
i
P_i
Pi，含义见题目描述。
输出格式
仅一行一个实数，代表最小的费用（四舍五入至小数点后两位）。
如果无法到达目的地，输出 No Solution。
输入输出样例 #1
输入 #1
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
输出 #1
26.95
说明/提示
保证
0
≤
N
≤
6
0 \\leq N \\leq 6
0≤N≤6，
0
≤
S
,
C
,
L
≤
500
0 \\leq S,C,L \\leq 500
0≤S,C,L≤500，且对于任意
0
≤
i
≤
N
0\\leq i \\leq N
0≤i≤N，均有
0
≤
P
i
≤
500
0 \\leq P_i \\leq 500
0≤Pi≤500，
0
≤
D
i
≤
S
0 \\leq D_i \\leq S
0≤Di≤S。
【题目解析】
算法原理如下：
1.枚举途中经过的加油站，每经过一个加油站，计算一次花费；
2.在一个加油站所需要加的油，就是能够支持它到达下一个油价比它低的加油站的量；
3.如果在这个加油站即使加满油，都不能到达一个比它油价低的加油站，就把油箱加满，前往能够到达的加油站中油价最低的那个；
4.如果在这个加油站即使加满油，都不能到达任意一个加油站，也不能到达终点城市，说明无解；
【贴上代码~】
#include <bits/stdc++.h>
using namespace std;
#define maxn 100000
#define db double
#define INF 9999999
int n;
db D1, D2, C, P, res, ans, maxx;
struct node
{
db co, dis;
bool friend operator <(const node& a, const node& b)
{ return a.dis < b.dis; }
}pl[maxn];
int Solve(int now)
{
int flag = INF; db d = pl[now].dis;
for(int i = now + 1; i <= n && pl[i].dis – d <= maxx; i ++)
{
if(pl[i].co < pl[now].co)
{
ans += ((pl[i].dis – d – res) / D2) * pl[now].co;
res = 0; return i;
}
if(flag == INF || pl[i].co < pl[flag].co) flag = i;
}
if(D1 – pl[now].dis <= maxx)
{
ans += ((D1 – pl[now].dis – res) / D2) * pl[now].co;
return INF;
}
if(flag == INF) { printf("No Solution\\n"); return –1; }
else
{
ans += C * pl[now].co; res += (maxx – (pl[flag].dis – d));
return flag;
}
}
int main()
{
scanf("%lf%lf%lf%lf%d", &D1, &C, &D2, &P, &n);
pl[0].dis = 0, pl[0].co = P;
for(int i = 1; i <= n; i ++)
scanf("%lf%lf", &pl[i].dis, &pl[i].co);
sort(pl, pl + n + 1);
maxx = C * D2;
int k = 0, t;
do
{
t = Solve(k), k = t;
if(t == –1) return 0;
}while(t != INF);
printf("%.2lf", ans);
return 0;
}
