d713 - 中位数

Sylveon

原題：http://zerojudge.tw/ShowProblem?problemid=d713
AC：http://zerojudge.tw/Submissions?problemid=d713&account=lfs92002

動態中位數，使用兩個Priority Queue來維護前後各一半的數列，使中位数浮到Priority Queue頂端。


使STL - Priority queue 能改為min-heap的作法在此是把比序的less改成greater，就可以顛倒順序。

(tmp)標籤測試，超噁心的方法終於成功了 ...(tag cpp)
/**********************************************************************************/
/*  Problem: d713 "中位数" from ACM 10107 c010:What is the Median? 加强版   */
/*  Language: CPP (666 Bytes)                                                     */
/*  Result: AC(0.1s, 3.8MB) judge by this@ZeroJudge                               */
/*  Author: lfs92002 at 2013-08-08 09:31:24                                       */
/**********************************************************************************/


#include<cstdio>
#include<queue>
#include<functional>
using namespace std;
#define LL long long
int main()
{
        priority_queue<LL,vector<LL>,greater<LL> > Mh;
        priority_queue<LL> mh;
        int i;
        while(~scanf("%lld",&i))
        {
                if(mh.size()==0)
                        mh.push(i);
                else if(mh.top()>i)
                        mh.push(i);
                else
                        Mh.push(i);
                if(mh.size()>Mh.size()+1)
                {
                        Mh.push(mh.top());
                        mh.pop();
                }
                else if(mh.size()+1<Mh.size())
                {
                        mh.push(Mh.top());
                        Mh.pop();
                }
                if(mh.size()==Mh.size())
                        printf("%lld\n",(mh.top()+Mh.top())/2);
                else if(mh.size()>Mh.size())
                        printf("%lld\n",mh.top());
                else
                        printf("%lld\n",Mh.top());
        }
}