原题：
旅行家的预算
时间限制: 1 Sec 内存限制: 125 MB题目描述
一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站ii离出发点的距离Di、每升汽油价格Pi（i=1,2,…,N）。计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。
输入
第一行，D1，C，D2，P，N。
接下来有N行。
第i+1行，两个数字，油站i离出发点的距离Di和每升汽油价格Pi。
输出
所需最小费用，计算结果四舍五入至小数点后两位。如果无法到达目的地，则输出“No Solution”。样例输入
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
样例输出
26.95
提示
N≤6,其余数字≤500
题意：
距离为d1的两个地点之间有n个......算了题目说的很清楚了。
变量含义：这道题字母比较多，首先把题中的字母的含义搞清楚，
D1：两地之间距离
D2：每升油可以行驶的路程
D[i] ( 1≤i≤n ) ：第i个加油站到起点的距离
C：油箱容量
n：加油站数量
P[i] ( 0≤i≤n ) ：第i个加油站每升油的价钱（包括起点）
这道题在洛谷中的标签是『贪心』『递归』，但是我打算用单调队列做。
先说一下整体的思路：可以现在读入的时候处理一下无解的情况，即就算油箱装满也跑不完全程，有这种情况的直接输出“No Solution”
因为不知道要买多少油，不妨假设油可以买进后任意时点地点转卖出。在起点先把油箱装满油，出发到下一个点（当然在路上花掉了一些油），我们假设我们可以控制花掉了哪些油——路上先花掉便宜的油，到达目的地后将比该地贵的油转卖出，最后装满该地的油。这里维护一个单调队列，使油的价钱单调上升，使用队头便宜的油，转卖队尾贵的油（注释在代码中）。
代码来啦——
1 #include<iostream>
2 #include<stdio.h>
3 #include<queue>
4 using namespace std;
5 const int N=505;
6 double c,d1,d2,oil,ans,d[N],p[N]; //c,d1,d2,d[],p[]如题意，oil指现有油量，ans即花费的钱
7 struct node{ double cost,v; }now; //队列储存结构体，包含买来的每种油的价钱(cost)和体积(v)
8 int n;
9 deque<node> q; //STL双端队列
10 int main()
11 {
12 scanf("%lf %lf %lf %lf %d",&d1,&c,&d2,&p[0],&n);
13 //两市之间的距离d1，油箱容量c，每升油能行驶的距离d214 //起点油价p[0]，加油站数量n
15 d[n+1]=d1; //把终点看成是第n+1个加油站
16 for(int i=1;i<=n;i++) scanf("%lf %lf",&d[i],&p[i]);
17 for(int i=2;i<=n+1;i++)
18 if(d[i]-d[i-1]>c*d2){ printf("No Solution"); return 0; } //如果油箱装满也跑不完说明没有解
19 ans=p[0]*c,oil=c;
20 q.push_back({p[0],c}); //起点加入所有油
21 for(int i=1;i<=n+1;i++)
22 {
23 double dis=d[i]-d[i-1],need=dis/d2; //need指需要几升油
24 while(!q.empty() && need>0)
25 {
26 now=q.front(); q.pop_front(); //取出已购买的油中最便宜的油
27 if(now.v>need)
28 {
29 oil-=need,now.v-=need;
30 q.push_front(now); //如果油够多把多余的油放回去
31 break;
32 }
33 oil-=now.v,need-=now.v; //否则全部使用
34 }
35 if(i==n+1) //如果已经到达终点
36 {
37 while(!q.empty()) //把所有多余的油都转售出去
38 {
39 now=q.front(); q.pop_front();
40 ans-=now.v*now.cost;
41 }
42 printf("%.2lf",ans);
43 return 0;
44 }
45 while(!q.empty() && q.back().cost>p[i]) //这一步是剔除已购买的油中的太贵的油，用该地较便宜的油替代，维护队列单调性
46 {
47 now=q.back(); q.pop_back();
48 oil-=now.v,ans-=now.v*now.cost; //如果购买的油的价钱高于当地就转卖，只剩下便宜的油
49 }
50 ans+=(c-oil)*p[i],q.push_back({p[i],c-oil}),oil=c; //将新购买的油加入队列，统计花费
51 }
52 return 0;
53 }
不注释的代码（点击左上角一键复制）——
1 #include<iostream>
2 #include<stdio.h>
3 #include<queue>
4 using namespace std;
5 const int N=505;
6 double c,d1,d2,oil,ans,d[N],p[N];
7 struct node{ double cost,v; }now;
8 int n;
9 deque<node> q;
10 int main()
11 {
12 scanf("%lf %lf %lf %lf %d",&d1,&c,&d2,&p[0],&n);
13 d[n+1]=d1;
14 for(int i=1;i<=n;i++) scanf("%lf %lf",&d[i],&p[i]);
15 for(int i=2;i<=n+1;i++)
16 if(d[i]-d[i-1]>c*d2){ printf("No Solution"); return 0; }
17 ans=p[0]*c,oil=c;
18 q.push_back({p[0],c});
19 for(int i=1;i<=n+1;i++)
20 {
21 double dis=d[i]-d[i-1],need=dis/d2;
22 while(!q.empty() && need>0)
23 {
24 now=q.front(); q.pop_front();
25 if(now.v>need)
26 {
27 oil-=need,now.v-=need;
28 q.push_front(now);
29 break;
30 }
31 oil-=now.v,need-=now.v;
32 }
33 if(i==n+1)
34 {
35 while(!q.empty())
36 {
37 now=q.front(); q.pop_front();
38 ans-=now.v*now.cost;
39 }
40 printf("%.2lf",ans);
41 return 0;
42 }
43 while(!q.empty() && q.back().cost>p[i])
44 {
45 now=q.back(); q.pop_back();
46 oil-=now.v,ans-=now.v*now.cost;
47 }
48 ans+=(c-oil)*p[i],q.push_back({p[i],c-oil}),oil=c;
49 }
50 return 0;
51 }