2018.12.05 codeforces 948C. Producing Snow（堆）

传送门
维护一个堆。
每次先算出一个都不弹掉的总贡献。
然后把要弹掉的弹掉，并减去它们对应的贡献。
代码：

#include<bits/stdc++.h> #define ri register int using namespace std; typedef long long ll; inline ll read(){ll ans=0;char ch=getchar();while(!isdigit(ch))ch=getchar();while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();return ans; } const int N=1e5+5; int n; ll ans=0,v[N],sum[N],t[N]; priority_queue<ll,vector<ll>,greater<ll> >q; int main(){n=read();for(ri i=1;i<=n;++i)v[i]=read();for(ri i=1;i<=n;++i){sum[i]=sum[i-1]+(t[i]=read()),q.push(sum[i-1]+v[i]);ans=t[i]*q.size();while(q.top()<=sum[i]&&q.size())ans+=q.top()-sum[i],q.pop();cout<<ans<<' ';}return 0; }

转载于:https://www.cnblogs.com/ldxcaicai/p/10084707.html

总结

以上是生活随笔为你收集整理的2018.12.05 codeforces 948C. Producing Snow（堆）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。