AtCoder
Leon |
03 Aug 2021
报告错误
如果你发现该网页中存在错误/显示异常，可以从以下两种方式向我们报告错误，我们会尽快修复：
- 使用 CS Club 网站错误 为主题，附上错误截图或描述及网址后发送邮件到 286988023@qq.com
- 在我们的网站代码仓库中创建一个 issue 并在 issue 中描述问题 点击链接前往Github仓库
题目描述
Takahashi有很多球，然后他可以做三种操做：
- 它可以将一个球，写上一个数字xi并放进包里。
- 将每一个包里的数字加上数字Xi。
- 拿出包里面最小的数的球
题目思路
利用priority queue的特性，将数据存进queue里面。并将所有的2的操作加起来的数储存起来，模拟将所有的数相加的过程。
复杂度分析：
priority queue的操作（基于小根堆实现) \(O(\log n)\)
遍历操作： \(O(n)\) 因为优先队列的操作实在遍历的情况下做的，所以两个复杂度相乘得到整体复杂度： \(O(n\log n)\)
代码实现
//qw.java
import java.util.*;
public class qw{
public static void main (String [] args){
Scanner in = new Scanner(System.in);
PriorityQueue <Long> queue = new PriorityQueue<Long>();
int n = in.nextInt();
long accumulate = 0L;
while(n-->0){
int type = in.nextInt();
if(type==1){
queue.add(in.nextLong()-accumulate);
}else if(type==2){
accumulate+=in.nextLong();
}else{
System.out.println(queue.poll()+accumulate);
}
}
}
}
