AtCoder Beginner Contest 212 D - Querying Multiset (优先队列+思维)

AtCoder Beginner Contest 212 D - Querying Multiset (优先队列+思维)

​​链接​​

题意：

三种操作：

向队列中放入一个x将队列中的数都+x拿出队列中最小的数，并输出。

分析：

首先我们知道本题的难点在于维护每次给队列中的数+x因为队列中的数加入的顺序不一样，所以第2种对队列中的贡献有的多有的少，(我说的不太清楚，谨慎理解)。 然后为了解决这个问题，我们可以将其转化成这样的 每次加上数我们用sum维护出来，之后，当我们进行第一种操作时，加入新数x，我们将起拆解成两部分 x=sum+y，我们向队列种添加y，这样队列中所有的数都在同一个基础上，都需要在最后+sum，这样就有可比性了，之后就用优先队列维护即可。

ll n;priority_queue,greater > q;void solve(){ cin>>n; ll sum=0; while(n--){ ll x,y; scanf("%lld",&x); if(x==1){ scanf("%lld",&y); q.push(y-sum); }else if(x==2){ scanf("%lld",&y); sum+=y; }else { printf("%lld\n",q-()+sum); q.pop(); } }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。