QAQ 开一个大根堆和一个小根堆,维护两个堆的数量小根堆=大根堆+1,输出小根堆的优先元素即为答案
#include <cstdio> #include <iostream> #include <algorithm> #include <queue> using namespace std; priority_queue <int> quex; priority_queue <int> qued; int main() { int n; int k=1; scanf("%d",&n); for(int i=1,a;i<=n;i++) { scanf("%d",&a); if(i==1) { quex.push(-a); printf("%d\n",a); continue; } if(a>quex.top()) quex.push(-a); else qued.push(a); if(quex.size()>qued.size()) { qued.push(-quex.top()); quex.pop(); } if(quex.size()<qued.size()) { quex.push(-qued.top()); qued.pop(); } if(i%2==1) { printf("%d\n",-quex.top()); } } }