【POJ 3784】 Running Median

【题目链接】

           http://poj.org/problem?id=3784

【算法】

           对顶堆算法

           要求动态维护中位数，我们可以将1-M/2（向下取整）小的数放在大根堆中，M/2+1-M小的数放在小根堆中

           每次插入元素时，先将插入元素与小根堆堆顶比较，如果比堆顶小，则插入小根堆，否则，插入大根堆，然后，判断两个堆

           的元素个数是否平衡，若不平衡，则交换两个堆的堆顶

【代码】

           

#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include   
#include <set>  
#include   
#include   
#include   
#include <string>  
#include   
#include   
#include   
#include   
#include   
#include  
using namespace std;
#define MAXN 10010

int i,t,n,tmp,len,T;
int a[MAXN],ans[MAXN];

struct BHeap
{
        int tot;
        int hp[MAXN];
        inline void clear()
        {
                tot = 0;
        }
        inline void Up(int pos)
        {
                int fa;
                if (pos == 1) return;
                fa = pos / 2;
                if (hp[pos] > hp[fa])
                {
                        swap(hp[pos],hp[fa]);
                        Up(fa);
                } 
        }
        inline void Down(int pos)
        {
                int son;
                son = pos * 2;
                if (son > tot) return;
                if (son < tot && hp[son+1] > hp[son]) son++;
                if (hp[son] > hp[pos])
                {
                        swap(hp[son],hp[pos]);
                        Down(son);
                }
        }
        inline void Insert(int x)
        {
                tot++;
                hp[tot] = x;
                Up(tot);
        }        
        inline void del()
        {
                swap(hp[1],hp[tot]);
                tot--;
                Down(1);
        }
        inline int get()
        {
                return hp[1];
        }
} B;
struct SHeap
{
        int tot;
        int hp[MAXN];
        inline void clear()
        {
                tot = 0;
        }
        inline void Up(int pos)
        {
                int fa;
                if (pos == 1) return;
                fa = pos / 2;
                if (hp[pos] < hp[fa])
                {
                        swap(hp[pos],hp[fa]);
                        Up(fa);
                } 
        }
        inline void Down(int pos)
        {
                int son;
                son = pos * 2;
                if (son > tot) return;
                if (son < tot && hp[son+1] < hp[son]) son++;
                if (hp[son] < hp[pos])
                {
                        swap(hp[son],hp[pos]);
                        Down(son);
                }
        }
        inline void Insert(int x)
        {
                tot++;
                hp[tot] = x;
                Up(tot);
        }        
        inline void del()
        {
                swap(hp[1],hp[tot]);
                tot--;
                Down(1);
        }
        inline int get()
        {
                return hp[1];
        }
} S;

int main() 
{
        
        scanf("%d",&T);
        while (T--)
        {
                len = 0;
                scanf("%d%d",&t,&n);
                S.clear(); B.clear();    
                for (i = 1; i <= n; i++) scanf("%d",&a[i]);
                for (i = 1; i <= n; i++)
                {
                        if (i == 1)
                        {
                                B.Insert(a[i]);
                                ans[++len] = a[i];
                                continue;
                        } 
                        if (a[i] <= B.get()) B.Insert(a[i]);
                        else S.Insert(a[i]);
                        if (B.tot - S.tot >= 1)
                        {
                                tmp = B.get();
                                B.del();
                                S.Insert(tmp);
                        }
                        if (S.tot - B.tot > 1)
                        {
                                tmp = S.get();
                                S.del();
                                B.Insert(tmp); 
                        }
                        if (i & 1) ans[++len] = S.get();
                }
                printf("%d %d\n",t,len);
                for (i = 1; i <= len; i++)
                {
                        if (i % 10 == 1) printf("%d",ans[i]);
                        else if (i % 10 == 0) printf(" %d\n",ans[i]);
                        else printf(" %d",ans[i]);
                }
                printf("\n");
        }
        
        return 0;
    
}

            

           

堆

相关

map文件堆栈大小

CDI关于堆栈溢出

《项目经理指导手册》 与我的一堆废话·！之一

内存泄漏和堆栈溢出的区别

基于堆排序的topk

js栈和堆的区别

数据结构与算法-二叉堆

buuoj [强网杯]随便注（堆叠注入,prepare预定义）

深入解析：Java内存分配之堆、栈和常量池

SQL注入之堆叠查询注入

SQL注入之堆叠查询注入

把石头分为若干堆

标签