解题思路
??对顶堆模板题,一个堆对应一半。
代码
priority_queue<int, vector<int>, less<int> > l, clears1;
priority_queue<int, vector<int>, greater<int> > r, clears2;
vector<int> ans;
int main(){
int t; scanf("%d", &t);
while(t--) {
int num, m; scanf("%d%d",&num,&m);
for (int i = 1; i<=m; ++i) {
int tmp; scanf("%d",&tmp);
//大根堆存[l,mid] 小根堆存[mid+1,r]
if(r.empty()||tmp>r.top()) r.push(tmp);
else l.push(tmp);
//维护两个堆的大小
while (l.size()>i/2) {
r.push(l.top());
l.pop();
}
while(l.size()<i/2) {
l.push(r.top());
r.pop();
}
if (i&1) ans.push_back(r.top());
}
printf("%d %d\n", num, (m+1)/2);
int sz = ans.size();
for (int i = 0; i<sz; ++i) printf("%d%c", ans[i], (i+1)%10==0?‘\n‘:‘ ‘);
if (sz%10) putchar(endl);
ans.clear(); l = clears1; r = clears2;
}
return 0;
}