- 分享
(堆)对顶堆
- 2024-10-5 16:23:28 @
详见洛谷P1168、P1801(黑匣子)模板题
#include<bits/stdc++.h>
using namespace std;
int n,a,x;
priority_queue<int>dgd;
priority_queue<int,vector<int>,greater<int> >xgd;
int main(){
ios::sync_with_stdio(false);cin.tie(0);
cin>>n>>x;cout<<x<<endl;
for(int i=2;i<=n;i++){
cin>>a;
if(dgd.size()<=xgd.size()){
if(x<a){
dgd.push(x);
x=a;
}
else dgd.push(a);
}
else{
if(x>a){
xgd.push(x);
x=a;
}
else xgd.push(a);
}
if(i%2){
if(x>xgd.top()){
int m=x;
x=xgd.top();
xgd.pop();
xgd.push(m);
}
if(x<dgd.top()){
int m=x;
x=dgd.top();
dgd.pop();
dgd.push(m);
}
cout<<x<<endl;
}
}
return 0;
}
0 条评论
目前还没有评论...