\(\text{Sol 1.}\)
考虑设计一个退流机制，我们将油设定为只有用了才计算价值，那么每次到一个加油站就直接加满，并且退掉耗费更大的油，然后优先使用价格小的油驶向下一个加油站，这个过程可以用单调队列维护，时间复杂度 \(\Theta(n)\)。
#include <bits/stdc++.h>
#define umap unordered_map
#define vint vector<int>
#define ll long long
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define ull unsigned long long
#define uint unsigned int
#define rg register
#define il inline
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define sqr(x) ((x)*(x))
using namespace std;
const int INF=0x3f3f3f3f;
inline int read(){int w=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){w=(w<<1)+(w<<3)+(ch^48);ch=getchar();}return w*f;
}
inline void write(int x){if(x<0){putchar('-');x=-x;}if(x>9) write(x/10);putchar(x%10+'0');
}#define db double
const db eps=1e-9;
const int N=7;
db d1,c,d2;
int n;
struct node{db p,d;
}a[10];
db ans;
struct oil{db p,rem;
};
int main(){#ifndef ONLINE_JUDGE//freopen("in.txt","r",stdin);#endifcin>>d1>>c>>d2>>a[0].p>>n;rep(i,1,n) cin>>a[i].d>>a[i].p;a[++n]={0,d1};deque<oil> Q;Q.push_back({a[0].p,c});for(int i=1;i<=n;++i){db dis=a[i].d-a[i-1].d;db add=0;while(1){if(Q.empty()){puts("No Solution");exit(0);}if(Q.front().rem*d2>=dis){ans+=Q.front().p*dis/d2;Q.front().rem-=dis/d2;add+=dis/d2;break;}else{ans+=Q.front().p*Q.front().rem;dis-=Q.front().rem*d2;add+=Q.front().rem;Q.pop_front();}}while(!Q.empty()&&Q.back().p>a[i].p) add+=Q.back().rem,Q.pop_back();// for(auto j:Q) add-=j.rem;Q.push_back({a[i].p,add});}printf("%.2lf\n",ans);#ifndef ONLINE_JUDGEfprintf(stderr,"%f\n",1.0*clock()/CLOCKS_PER_SEC);#endifreturn 0;
}
\(\text{Sol 2.}\)
没到一个加油站有几种选择：加满，加到恰好能到下一个加油站。暴力即可，时间复杂度 \(\Theta(2^n)\)，实际跑不满。
参考这篇题解。
\(\text{Sol 3.}\)
也是贪心，比解法一好想，但个人觉得不如解法一优美。
考虑在当前加油站做的决策，首先至少得到下一个加油站，然后考虑加不加满，目标直指第一个价格更低的加油站，否则找下一个价格最低的，中间过程判无解。
参考这篇题解。