《算法进阶指南》—0x05:Running Median(优先队列,堆排序★★☆)
Running Median
https://ac.nowcoder.com/acm/problem/50940
思路:
1:维护一个最大堆和一个最小堆,若元素数量为1,直接输出即可。否则首先先将前两个元素中较大的加入最小堆,较小的加入最大堆。
2:然后每次添加新元素的时候,先将其与最大堆和最小堆的堆顶进行对比,如果其大于最小堆堆顶则插入最小堆,如果其小于最大堆堆顶则插入最大堆,否则选择元素数量较小的一堆。
3: 每次插入结束后如果两堆的元素数量差大于1则从元素数量较多的一堆中取出堆顶插入另一堆,这样可以保证两堆元素数量始终是平衡的。 在这种情况下,选取中位数只需要选取元素数量多 1 的一堆的堆顶即可。
4:注意输出格式!
code:
#include <iostream> #include <cstdio> #include <iomanip> #include <cstring> #include <string> #include <cmath> #include <string> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <list> #include <algorithm> #include <functional> typedef long long ll; using namespace std; priority_queue<int, vector<int>, greater<int>> mx; priority_queue<int, vector<int>, less<int>> mi; void clear(priority_queue<int, vector<int>, less<int>>& mi) { priority_queue<int, vector<int>, less<int>> empty; swap(empty, mi); } void clear(priority_queue<int, vector<int>, greater<int>>& mi) { priority_queue<int, vector<int>, greater<int>> empty; swap(empty, mi); } ll read() { ll s = 0, f = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0'; ch = getchar(); } return s * f; } int main() { std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #ifdef ak freopen("in.txt", "r", stdin); freopen("out.txt", "w", stdout); #endif int p, m, t; p = read(); while (p--) { ll sum = 1; t = read(); m = read(); int w; cout << t << " " << (m + 1) / 2 << endl; if (m == 1) { w = read(); cout << w << endl; continue; } int t1, t2, t; t1 = read(); t2 = read(); mx.push(max(t1, t2)); mi.push(min(t1, t2)); cout << t1 << " "; for (int i = 3; i <= m; i++) { w = read(); if (w >= mx.top()) { mx.push(w); } else if (w <= mi.top()) { mi.push(w); } else if (mi.size() >= mx.size()) { mi.push(w); } else { mx.push(w); } int kk = mx.size() - mi.size(); while (abs(kk) >= 2) { if (mx.size() > mi.size()) { int temp = mx.top(); mx.pop(); mi.push(temp); } else if (mi.size() > mx.size()) { int temp = mi.top(); mi.pop(); mx.push(temp); } kk = mx.size() - mi.size(); } if (i & 1) { sum++; if (mi.size() > mx.size()) { cout << mi.top() << " "; } else { cout << mx.top() << " "; } if (sum % 10 == 0) { cout << endl; } } } if (sum % 10) { cout << endl; } sum = 0; clear(mi); clear(mx); } return 0; }
算法竞赛进阶指南 文章被收录于专栏
1