NC50940 Running Median

题目地址：

https://ac.nowcoder.com/acm/problem/50940

基本思路：

解法一

我们维护一个大顶堆,一个小顶堆,并且维护这样一个状态即大顶堆最大的数,小于小顶堆最小的那个数,即是满足大顶堆里存放的是前一半数,小顶堆里存放的是后一半数,当为奇数索引并保持以上状态的情况下,大顶堆里多出来的那个数即是答案。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int 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 INF 0x3f3f3f3f
int cas,n,x;
signed main() {
  IO;
  int t;
  cin >> t;
  while (t-- > 0) {
    cin >> cas >> n;
    priority_queue<int, vector<int>, less<>> q1;//大顶堆;
    priority_queue<int, vector<int>, greater<>> q2;//小顶堆;
    vector<int> ans;
    rep(i, 1, n) {
      cin >> x;
      if (i % 2) q1.push(x);//奇数时多出来的那个数在大顶堆;
      else q2.push(x);
      if (!q1.empty() && !q2.empty()) {
        int a = q1.top(), b = q2.top();
        if (a > b) {//要维护大顶堆的最大,小于小顶堆的最小;
          q1.pop(); q2.pop();
          q1.push(b), q2.push(a);
        }
      }
      if (i % 2) ans.push_back(q1.top());
    }
    cout << cas << " " << ans.size() << '\n';
    int cnt = 0;
    for (auto it : ans) {
      cnt++;
      cout << it << " ";
      if (cnt % 10 == 0) cout << "\n";
    }
    cout << "\n";
  }
  return 0;
}

解法二

用pbds库的红黑树水过,直接在索引是奇数的时候暴力找前面的第(i/2 + 1)大,大家有兴趣还是可以百度学一下pbds库的。

参考代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#include <bits/extc++.h>//使用pbds库需要引入的;
using namespace std;
using namespace __gnu_pbds;//使用pbds库需要引入的;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int 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 INF 0x3f3f3f3f
//pbds库自含的红黑树的定义方法,具体大家可以百度;
typedef tree<pair<int,int>,null_type,less<>,rb_tree_tag,tree_order_statistics_node_update> rbtree;
int n,x,cas;
signed main() {
  IO;
  int t;
  cin >> t;
  while (t-- > 0) {
    cin >> cas >> n;
    rbtree st;
    vector<int> ans;
    rep(i, 1, n) {
      cin >> x;
      st.insert({x, i});//用pair是防止它去重;
      if (i % 2) {
        int tmp = i / 2 + 1;
        ans.push_back(st.find_by_order(tmp - 1)->first);
      }
    }
    cout << cas << " " << ans.size() << '\n';
    int cnt = 0;
    for (auto it : ans) {
      cnt++;
      cout << it << " ";
      if (cnt % 10 == 0) cout << "\n";
    }
    cout << "\n";
  }
  return 0;
}