题目传送门(以纪念调了两个半小时的单调队列)


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[],p[],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=,fix=;
while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;
do ret=(ret<<)+(ret<<)+ch-''; while(isdigit(ch=getchar()));
return ret*fix;
} inline double g()
{
double ret=lf(),d=;
if(ch=='.') while(isdigit(ch=getchar())) ret+=(ch^)/(d*);
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[], &n);//scanf保平安(哪位大佬看出我快读的问题麻烦指明一下QAQ(加快读只过了两个点))
for(R i=;i<=n;i++) {scanf("%lf%lf",&d[i],&p[i]); if(d[i]-d[i-]>C*d2) {printf("No Solution"); return ;}}
    //如果油箱加满,都不能到下一个加油站,那就无解
d[n+]=d1;crt=C;//在起点加满油
q.push_back(node(p[],C));
ans+=p[]*C;//在起点加满油
for(R i=;i<=n+;i++)
{
db drt=(d[i]-d[i-])/d2;//当前经过[d[i-1],d[i]]所需油量
while(!q.empty()&&drt>)
{
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+)
{
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\n",ans);
}

如有错误,恳请您指正(我太菜了);如有不理解,可留言,我会尽量回复。。。(高中生(逃)。。)

by Jackpei 2019.2.27

最新文章

  1. Python for Infomatics 第13章 网页服务一(译)
  2. 我的ORM之五-- 事务
  3. Android学习笔记——ListView
  4. Java集合源码学习(四)HashMap分析
  5. js中const,var,let区别
  6. IOS基础之设置APP的名字、设置图标、添加等待加载时的图片
  7. PowerDesigner 面向对象模型(OOM)
  8. Python获取Origin官网视频
  9. JQuery 获取指定url对应的html内容
  10. MYSQL ERROR 1045 (28000): Access denied for user &#39;neeky&#39;@&#39;Nee&#39; (using password: YES)
  11. 使用ActionBarActivity或者RxAppCompatActivity或者AppCompatActivity闪退的问题
  12. Docker(3):Dockerfile配置详解
  13. VMware 设置网络
  14. 日志入库-log4j-mysql连接中断问题
  15. Mac 上有哪些鲜为人知且极大提高效率的工具?
  16. Codeforces 999F Cards and Joy(二维DP)
  17. 使用DLL在进程间共享数据
  18. 【CentOS】安装部署jenkins从git获取代码[转]
  19. SpringBoot实现监听redis key失效事件
  20. Shell脚本中字符串判空:使用-z 字符串长度为0时,为真,-n字符串长度不为0,为真。这两个都不靠谱【转】

热门文章

  1. JAVA- 成员变量与局部变量的区别
  2. Cocos2d-x中定时器的使用
  3. linux应用之nginx的源码安装及配置(centos)
  4. (转)C语言之原码、反码和补码
  5. HihoCoder1644 : 完美命名的烦恼([Offer收割]编程练习赛37)(有向图的一笔画问题||欧拉路)
  6. Node初学者入门,一本全面的NodeJS教程
  7. 洛谷P1144——最短路计数
  8. win7-64 mysql的安装
  9. 如何用CSS实现矩形按钮右边缘的中间有个往里凹的小半圆
  10. linux下如何使用Mysql