竹園論壇

標題: d713 - 中位数 [打印本頁]

作者: Sylveon 時間: 2014-5-6 15:05
標題: d713 - 中位数
原題：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());
      }
}

歡迎光臨竹園論壇 (http://forum.tfcis.org/)