Running Median

题目链接：Running Median

Description

给定一个数列 ，你需要输出前个数中的中位数分别是多少。
多组数据。
数据范围

Solution

我们先考虑暴力。
对于前个数，我们可以用一个桶来记录一下所有数的出现情况，然后取第个数即可。
考虑如何优化暴力。
我们发现，从前个数到前个数，其实只是新加了两个数和，所以我们可以用数据结构来维护。
我们考虑用两个优先队列来模拟这一过程。
第一个优先队列（大根堆），我们用来维护这个数中从小到大，排名小的数集合；
第二个优先队列（小根堆），我们用来维护这个数中从小到大，排名小的数集合。
显然中位数就是第二个优先队列的头。
每次新加入一个数，如果这个数比中位数小，则插入第一个优先队列中；否则插入第二个优先队列中。
我们考虑一种情况：加入数后破坏了两个优先队列个数的性质。
那么，如果某一个优先队列中的元素过多/过少，那么就从另一个优先队列的头中给予/挪动几个元素，使其达到均衡。
这样，我们每次都可以实现动态查询中位数，这题就算结束啦。
时间复杂度

Code

// Author: wlzhouzhuan
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ull unsigned long long
#define rint register int
#define rep(i, l, r) for (rint i = l; i <= r; i++)
#define per(i, l, r) for (rint i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define Each(i) for (rint i = head[u]; i; i = edge[i].nxt)
inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

const int N = 10005;
int a[N];
int m, n;

int main() {
  int T = read();
  while (T--) {
    priority_queue <int> p1; // 第一个优先队列，是个大根堆 
    priority_queue <int, vector <int>, greater <int>> p2; // 第二个优先队列，是个小根堆 
    m = read(), n = read();
    printf("%d %d\n", m, (n + 1) >> 1);
    for (rint i = 1; i <= n; i++) a[i] = read();
    p2.push(a[1]);
    printf("%d ", a[1]);
    int cur = 1;
    for (rint i = 2; i <= n; i++) {
      if (a[i] > p2.top()) {
        p2.push(a[i]);
      } else {
        p1.push(a[i]);
      }
      if (i & 1) {
        // 调整 
        while (p1.size() > (i - 1) / 2) { 
          p2.push(p1.top());
          p1.pop();
        }
        while (p2.size() > (i + 1) / 2) {
          p1.push(p2.top());
          p2.pop();
        }
        cur++;
        printf("%d", p2.top());
        if (cur % 10 == 0) putchar('\n');
        else putchar(' ');
      }
    }
    if (cur % 10 != 0) {
      putchar('\n');
    }
  }
  return 0;
}