POJ 1442 Black Box（優先隊列+對頂堆）

​​傳送門​​

題目大意

思路

代碼

ll u[maxn],a[maxn];
//小根堆維護大于等于目前節點的數
//大根堆維護小于目前節點的數
//然後來回抛 
priority_queue<ll,vector<ll>,greater<ll> > qx;
priority_queue<int> qd;

int main(){
  int m,n;
  scanf("%d%d",&m,&n);
  for(int i=1;i<=m;i++){
    scanf("%lld",&a[i]);
  }
  for(int i=1;i<=n;i++){
    scanf("%lld",&u[i]);
  }
  int x=0;//目前節點值 
  int cnt=1;
  for(int i=1;i<=m;i++){
    if(qd.size()==0){
      qd.push(a[i]);
    }
    else{
      if(a[i]<qd.top()){
        qd.push(a[i]);
      }
      else{
        qx.push(a[i]);
      }
    }
    while(u[cnt]==i){
      x++;
      cnt++;
      while(qd.size()!=x){
        if(qd.size()>x){
          qx.push(qd.top());
          qd.pop();
        }
        else{
          qd.push(qx.top());
          qx.pop();
        }
      }
      ll xx=qd.top();
      printf("%lld\n",xx);
    }
  } 
}