題目描述
一個旅行家想駕駛汽車以最少的費用從一個城市 到另一個城市（假設出發時油箱是空的）。給定兩個城市之間的距離D1、汽車油箱的容量C（以升為單位）、每升汽油能行駛的距離D2、出發點每升汽油價格P 和沿途油站數N（N可以為零），油站i離出發點的距離Di、每升汽油價格Pi（i=1，2，……N）。計算結果四舍五入至小數點后兩位。如果無法到達目的 地，則輸出“No Solution”。
輸入
第一行為4個實數D1、C、D2、P與一個非負整數N；
接下來N行，每行兩個實數Di、Pi。
輸出
如果可以到達目的地，輸出一個實數（四舍五入至小數點后兩位），表示最小費用；否則輸出“No Solution”（不含引號）。
樣例輸入
275.6 11.9 27.4 2.8 2
102.0 2.9
220.0 2.2
樣例輸出
26.95
思路：很明顯的一個貪心題目（ps：不知道dp能不能做）。
對于我們當前的位置，我們很希望可以一下子跑到油價比當前位置便宜的地方。如果不能的話，我們只能把當前油箱裝滿，然后跑到下一個加油站，再重復這個操作。那么怎么找出油價比當前位置便宜的地方呢？利用單調棧來實現這一步驟。然后去執行上面的操作就可以了。
代碼如下：

#include<bits/stdc++.h> #define ll long long using namespace std;const int maxx=1e5+100; struct node{double pos,val;bool operator<(const node &a)const{return pos<a.pos;} }p[maxx]; double val[maxx]; double D1,C,D2,P; int R[maxx]; int n;int main() {scanf("%lf%lf%lf%lf%d",&D1,&C,&D2,&P,&n);for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].pos,&p[i].val);sort(p+1,p+1+n);p[n+1].pos=D1;p[n+1].val=0.0;p[0].pos=0.0;p[0].val=P;val[0]=P;for(int i=1;i<=n;i++) val[i]=p[i].val;stack<int> s;for(int i=n;i>=0;i--){while(s.size()&&val[s.top()]>val[i]) s.pop();if(!s.size()) R[i]=n+1;else R[i]=s.top();s.push(i); }double ans=0.0,res=0.0;//res代表當前剩的油int flag=1;for(int i=0;i<=n;){double no=(p[R[i]].pos-p[i].pos)/D2;if(no<=C) {ans+=max(no-res,0.0)*p[i].val;if(no>res) res=0.0;else res-=no;i=R[i];}else{no=(p[i+1].pos-p[i].pos)/D2;if(no>C) flag=0;ans+=(C-res)*p[i].val;res=C-no;i++;}}if(flag==0) cout<<"No Solution"<<endl;else printf("%.2lf\n",ans);return 0; }

努力加油a啊，(^o)/~

總結

以上是生活随笔為你收集整理的[蓝桥杯][算法训练VIP]旅行家的预算（单调栈+贪心）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。