一看到题目想到是贪心加模拟，但是一直在纠结在某个车站要不要加油，加多少油，加少了便走不完，加多了价格就不是最优的，一直被绕在这里面，后面看了题解才有点明白。 整体思路就是在输入数据的时候便可以判断能不能到达重点，因为计算出满油状态下车能走的最远距离，与这些加油站之间距离比较即可，接下来就是判断怎么价格最低。我们需要保证每次走路径烧的油都是当前状态的最低价格，可采用单调队列来做，经过每个加油站，比较当前油箱内哪些没用的油比当前价贵，把这些油退掉换成当前油，每次都把油加到满，最后把油箱你内剩余的油退掉即可。
#include<bits/stdc++.h> using namespace std; typedef pair<double,double> PII; double D1,C,D2,P; int N; double a[505]; double p[505]; struct Node{ double px;//单价 double c;//油量 Node(double temp1,double temp2){ px=temp1; c=temp2; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>D1>>C>>D2>>P>>N; double maxl=D2*C; a[0]=0; p[0]=P; bool vis=0; for(int i=1;i<=N;i++){ cin>>a[i]>>p[i]; if(a[i]-a[i-1]>maxl){ vis=1; } } a[N+1]=D1; if(D1-a[N]>maxl) vis=1; if(vis){ cout<<"No Solution"<<endl; return 0; } deque<Node> YHT; double cnt=C*P; double now=C; YHT.push_back(Node(P,C)); for(int i=1;i<=N+1;i++) { double need=(a[i]-a[i-1])/D2;//需要的油 while(YHT.size()&&need>0){ Node temp=YHT.front();//选择最便宜的邮 YHT.pop_front(); if(temp.c>need){//如果没用完，继续放入 temp.c-=need; now-=need; need=0; YHT.push_front(temp); } else { now-=need; need-=temp.c; } } if(i==N+1)//到达终点退油即可 { while(YHT.size()){ Node temp=YHT.front(); cnt-=temp.c*temp.px; YHT.pop_front(); } cout<<fixed<<setprecision(2)<<cnt<<endl; return 0; } while(YHT.size()&&p[i]<YHT.back().px)//退掉比当前贵的油 { Node temp=YHT.back(); now-=temp.c; cnt-=temp.c*temp.px; YHT.pop_back(); } cnt+=(C-now)*p[i];//加满 YHT.push_back(Node(p[i],C-now)); now=C; } }