题目传送门（以纪念调了两个半小时的单调队列）
emmm这题单调队列可海星...
因为每个点有油量无限的，但是油箱容量是有限的（正好反的一道题 SP348 EXPEDI - Expedition）
所以我们可以用一个价格递减单调队列来记录已加过油的加油站
若要行驶到一个新的加油站时，弹出对头，直到油量可以支撑到这个加油站，然后判断到没到终点，再然后弹出对尾，直到对尾的价格小于这个加油站的价格（之前的状态都可以去掉，因为每个加油站油量是无限的，你在开头就已经判断了，就算你到了这个加油站油箱空了，你也可以到下一个加油站）（就是某ddy dalao说的贪心反悔），最后把这个点的价格，和可以加的油量插入队尾
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> #define R register int #define db double using namespace std; int n; db d1,C,d2,d[10],p[10],ans,crt; char ch; struct node{ db p,c;//p代表价格，c代表在油箱还剩下的冗余油量 node(db pi,db ci): p(pi),c(ci) {} }; deque<node> q; inline int lf() { R ret=0,fix=1; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; do ret=(ret<<3)+(ret<<1)+ch-'0'; while(isdigit(ch=getchar())); return ret*fix; } inline double g() { double ret=lf(),d=1; if(ch=='.') while(isdigit(ch=getchar())) ret+=(ch^48)/(d*10); return ret; } signed main() { //d1=g(),C=g(),d2=g(),p[0]=g(),n=g(); scanf("%lf%lf%lf%lf%d", &d1, &C, &d2, &p[0], &n);//scanf保平安（哪位大佬看出我快读的问题麻烦指明一下QAQ（加快读只过了两个点）） for(R i=1;i<=n;i++) {scanf("%lf%lf",&d[i],&p[i]); if(d[i]-d[i-1]>C*d2) {printf("No Solution"); return 0;}}
//如果油箱加满，都不能到下一个加油站，那就无解 d[n+1]=d1;crt=C;//在起点加满油 q.push_back(node(p[0],C)); ans+=p[0]*C;//在起点加满油 for(R i=1;i<=n+1;i++) { db drt=(d[i]-d[i-1])/d2;//当前经过[d[i-1],d[i]]所需油量 while(!q.empty()&&drt>0) { node front=q.front();q.pop_front(); if(front.c>drt) {crt-=drt; q.push_front(node(front.p,front.c-drt)); break;}
//弹队头：当一个位置已经没有冗余的油量时，就弹掉。 crt-=front.c,drt-=front.c; } if(i==n+1) { while(!q.empty()) ans-=q.front().p*q.front().c,q.pop_front(); break; } while(!q.empty()&&q.back().p>p[i]) ans-=q.back().c*q.back().p,crt-=q.back().c,q.pop_back(); ans+=(C-crt)*p[i]; q.push_back(node(p[i],C-crt)); crt=C; } printf("%.2lf ",ans); }
如有错误，恳请您指正（我太菜了）；如有不理解，可留言，我会尽量回复。。。（高中生(逃)。。）
by Jackpei 2019.2.27