NC50940 Running Median
Running Median
https://ac.nowcoder.com/acm/problem/50940
NC50940 Running Median
题目地址：
基本思路：
解法一
我们维护一个大顶堆,一个小顶堆,并且维护这样一个状态即大顶堆最大的数,小于小顶堆最小的那个数,即是满足大顶堆里存放的是前一半数,小顶堆里存放的是后一半数,当为奇数索引并保持以上状态的情况下,大顶堆里多出来的那个数即是答案。
参考代码：
#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;
}
