POJ 3784.Running Median

2015-07-16

问题简述：

　　动态求取中位数的问题，输入一串数字，每输入第奇数个数时求取这些数的中位数。

　　原题链接：http://poj.org/problem?id=3784

解题思路：

　　求取中位数的方法常常想到使用堆来实现：取一个大顶堆，一个小顶堆，使大顶堆的堆顶记录中位数，因此，要时刻保持大顶堆堆顶元素小于小顶堆堆顶元素，且大顶堆元素个数等于小顶堆元素个数或等于小顶堆元素个数加一。

　　以下有两种堆得实现方法：

　　　　一：直接使用STL中的函数（make_heap,push_heap,pop_heap,sort_heap）实现堆；

　　　　二：使用优先队列（priority_queue）实现堆；

方法一源码：

 /*

 OJ: POJ

 ID: 3013216109

 TASK: 3784.Running Median

 LANG: C++

 NOTE: 堆(STL)

 */

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int MAX=;

 int a[MAX],b[MAX],c[MAX];

 bool cmp(int a,int b) {

     return a>b;

 }

 int main()

 {

     int t,n,m,x;

     scanf("%d",&t);

     while(t--) {

         scanf("%d %d",&n,&m);

         int a_len=,b_len=,k=,i=;

         while(m--) {

             i++;

             scanf("%d",&x);

             if(a_len==) {

                 a[]=x;

                 c[k++]=x;

                 a_len++;

                 continue;

             }

             if(x<=a[]) {

                 a[a_len++]=x;

                 push_heap(a,a+a_len);

             }

             else {

                 b[b_len++]=x;

                 push_heap(b,b+b_len,cmp);

             }

             while(a_len>b_len+) {

                 b[b_len++]=a[];

                 pop_heap(a,a+a_len);

                 a_len--;

                 push_heap(b,b+b_len,cmp);

             }

             while(a_len<b_len) {

                 a[a_len++]=b[];

                 pop_heap(b,b+b_len,cmp);

                 b_len--;

                 push_heap(a,a+a_len);

             }

             if(i%==)

                 c[k++]=a[];

         }

         printf("%d %d\n",n,k);

         for(int i=;i<k;i++) {

             if(i>&&i%==) putchar('\n');

             if(i%) putchar(' ');

             printf("%d", c[i]);

         }

         printf("\n");

     }

     return ;

 }

方法二源码：

 /*

 OJ: POJ

 ID: 3013216109

 TASK: 3784.Running Median

 LANG: C++

 NOTE: 堆(优先队列)

 */

 #include <cstdio>

 #include <queue>

 #define MAX 10005

 using namespace std;

 priority_queue<int,vector<int>,less<int> > a;    //大顶堆

 priority_queue<int,vector<int>,greater<int> > b; //小顶堆

 vector<int> c;

 int main()

 {

     int t,n,m,x;

     scanf("%d",&t);

     while(t--) {

         scanf("%d %d",&n,&m);

         while(!a.empty()) a.pop();

         while(!b.empty()) b.pop();

         c.clear();

         for(int i=;i<m;i++) {

             scanf("%d",&x);

             if(a.empty()) {

                 a.push(x);

                 c.push_back(x);

                 continue;

             }

             if(x<=a.top())

                 a.push(x);

             else

                 b.push(x);

             while(a.size()>b.size()+) {

                 b.push(a.top());

                 a.pop();

             }

             while(a.size()<b.size()) {

                 a.push(b.top());

                 b.pop();

             }

             if(i%==&&i!=)

                 c.push_back(a.top());

         }

         printf("%d %d\n",n,(m+)/);

         for(int i=;i<c.size();i++) {

             if(i>&&i%==) putchar('\n');

             if(i%) putchar(' ');

             printf("%d", c[i]);

         }

         printf("\n");

     }

     return ;

 }