动态维护第k大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
priority_queue<int> a; //大根堆
priority_queue<int,vector<int>,greater<int> > b;

for(int i=1; i<=n; i++){
  int x; scanf("%d",&x);
  if(b.empty()||x>=b.top()) b.push(x); //插入
  else a.push(x);
  
  int k=max(1,i*w/100); //第k大
  while(b.size()>k) a.push(b.top()), b.pop(); //调整
  while(b.size()<k) b.push(a.top()), a.pop();
  printf("%d ", b.top()); //取值
}