solution
题目就是要求对于每奇数个数字,输出其中位数。
我们只要维护两个堆,第一个大根堆维护较小的数字,第二个小根堆维护较大的个数字。每当新加入一个数字的时候将其与大根堆的队首比较,并维护两个堆的大小。
要求的中位数就是大根堆里的最大值。
code
/* * @Author: wxyww * @Date: 2020-04-08 20:09:02 * @Last Modified time: 2020-04-08 20:20:57 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cmath> #include<ctime> #include<bitset> #include<cstring> #include<algorithm> #include<string> #include<queue> #include<vector> using namespace std; typedef long long ll; const int N = 10010; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } priority_queue<ll>q1; priority_queue<ll,vector<ll>,greater<ll> >q2; int main() { // freopen("1.in","r",stdin); int T = read(); while(T--) { while(!q1.empty()) q1.pop(); while(!q2.empty()) q2.pop(); int num = read(),n = read(); printf("%d %d\n",num,(n + 1) >> 1); q1.push(read()); int now = 1; printf("%lld ",q1.top()); for(int i = 2;i <= n;++i) { ll x = read(); if(x > q1.top()) q2.push(x); else q1.push(x); if(i & 1) { while(q1.size() > q2.size()) {q2.push(q1.top());q1.pop();} while(q2.size() >= q1.size()) {q1.push(q2.top());q2.pop();} printf("%lld ",q1.top()); ++now; if(now % 10 == 0) puts(""); } } if(now % 10) puts(""); } return 0; } /* 1 2 9 9 8 7 6 5 4 3 2 1 */