LGOJ P1168 中位数 解题报告

LGOJ P1168 中位数 解题报告

文章目录

• 题目链接
• 解题思路
• 详细代码

题目链接

LGOJ P1168 中位数

解题思路

我们要维护一个长度不断增加的序列的中位数，一般能想到的做法是动态开点线段树。但是，实际上，我们可以使用堆来维护。
我们使用两个堆来维护当前的序列。
一个是大根堆，维护序列的前半段，一个是小根堆，维护序列的后半段。
加入元素时，若其比大根堆的堆顶还大，它理应放在序列的后半段，即放入小根堆里。反之同理。
接下来要做的就是调整了。使大根堆、小根堆的元素个数差不多，最多相差一个。
然后，只要输出元素多的那个堆的堆顶，就是要求的中位数了。

详细代码

#define USEFASTERREAD 1 #define rg register
#define inl inline
#define DEBUG printf("[Passing [%s] in line %d.]n", __func__, __LINE__)
#define putline putchar('n')
#define putsp putchar(' ')
#define Rep(a, s, t) for(rg int a = s; a <= t; a++)
#define Repdown(a, t, s) for(rg int a = t; a >= s; a--)
typedef long long ll;
#include<cstdio>#if USEFASTERREAD
char In[1 << 20], *ss = In, *tt = In;
#define getchar() (ss == tt && (tt = (ss = In) + fread(In, 1, 1 << 20, stdin), ss == tt) ? EOF : *ss++)
#endif
struct IO {void RS() {freopen("test.in", "r", stdin), freopen("test.out", "w", stdout);} template<typename T> inline IO r(T& x)const	{x = 0; T f = 1; char ch = getchar();for(; ch < '0' || ch > '9'; ch = getchar()) if(ch == '-') f = -1;for(; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + int(ch - '0');x *= f; return *this;}template<typename T> inline IO w(T x)const {if(x < 0) {putchar('-'); x = -x;}if(x >= 10) w(x / 10);putchar(x % 10 + '0'); return *this;}template<typename T> inline IO wl(const T& x)const {w(x), putline; return *this;}template<typename T> inline IO ws(const T& x)const {w(x), putsp; return *this;}inline IO l() {putline; return *this;}inline IO s() {putline; return *this;}
}io;
template<typename T> inline T Max(const T& x, const T& y) {return y < x ? x : y;}
template<typename T> inline T Min(const T& x, const T& y) {return y < x ? y : x;}
template<typename T> inline void Swap(T& x, T& y) {T tmp = x; x = y; y = tmp;}
template<typename T> inline T Abs(const T& x) {return x > 0 ? x : -x;} 
#include<queue>
using namespace std;
int n;priority_queue<int> B;//大根堆，存前半段 
priority_queue<int, vector<int>, greater<int> > S;//小根堆，存后半段 int main() {//io.RS();int t; io.r(n);io.r(t);B.push(t);io.wl(t);for(rg int i = 2; i <= n; i++) {io.r(t);if(t > B.top()) S.push(t);else B.push(t);while(S.size() > B.size() + 1) B.p()), S.pop();while(B.size() > S.size() + 1) S.p()), B.pop();if(i & 1) io.wl(S.size() > B.size() ? S.top() : B.top());}	return 0;	
}