arc072f Dam
2021/8/23 23:06:12
本文主要是介绍arc072f Dam,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
对于第i天,我们要给它腾出位置,为了使温度最高,要删除的时前面温度最低的。
对于一个新加入的温度,如果它比之前的温度都要高。直接加入即可。
如果它不是最高温,我们把它与前一个温度混合,直到混合后的温度是最高温。
原因如下:
对于之后加入的温度,我们要么踢掉一部分之前的混合液t2,把它与当前的温度t1混合,要么把它与t1与之前的混合液t2混合的温度t3混合,再踢掉一部分t3以腾出空间(这样可以得到t1<t2<t3)
那么我们显然选择的是t3(温度更高),所以对于这种情况我们要把它与前面的混合
这个我们只要维护一个单调递增的单调队列来维护温度就行了。
代码
#include<bits/stdc++.h> using namespace std; #define N 500010 int st,ed; struct data { double t,v; } datas[N],q[N]; data merge(data a,data b) { data c; c.v=a.v+b.v; c.t=(a.t*a.v+b.t*b.v)/c.v; return c; } signed main() { int n,l; cin>>n>>l; for(int i=1; i<=n; i++) { scanf("%lf%lf",&datas[i].t,&datas[i].v); } double sum=0,tot=0; q[st=ed=1]=datas[1],sum=datas[1].v,tot=datas[1].t*datas[1].v; printf("%lf\n",datas[1].t); for(int i=2; i<=n; i++) { q[++ed]=datas[i],tot+=datas[i].v*datas[i].t,sum+=datas[i].v; while(ed>st&&sum>l) { if(sum-q[st].v>=l) { tot-=q[st].v*q[st].t; sum-=q[st].v; st++; } else { q[st].v-=sum-l; tot-=(sum-l)*q[st].t; sum-=sum-l; } } while(ed>st) { if(q[ed].t>=q[ed-1].t) break; data d=merge(q[ed],q[ed-1]); q[--ed]=d; } printf("%.10f\n",tot/sum); } }
这篇关于arc072f Dam的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-30uniAPP 实现全屏左右滚动滚动的效果-icode9专业技术文章分享
- 2024-06-30如何在本地使用授权或插件-icode9专业技术文章分享
- 2024-06-30伪静态规则配置方法汇总-icode9专业技术文章分享
- 2024-06-29易优CMS安装常见问题汇总-icode9专业技术文章分享
- 2024-06-28易优新手必读安装教程-icode9专业技术文章分享
- 2024-06-28忘记eyoucms后台密码怎么办?-icode9专业技术文章分享
- 2024-06-26终极指南:Scrum中如何设置需求优先级
- 2024-06-26AI大模型企业应用实战(25)-为Langchain Agent添加记忆功能
- 2024-06-26小白家庭 nas 搭建方案-icode9专业技术文章分享
- 2024-06-23AI大模型企业应用实战(14)-langchain的Embedding