POJ-3481 Double Queue,Treap树和set花式水过！

Double Queue

本打算学二叉树，单纯的二叉树感觉也就那几种遍历了，无意中看到了这个题，然后就花了两天时间又去学了学Treap树，真的不好理解，真应该从基础开始的，但我比较倔强，看到这题一定要先做了再说。上午和某公众号交流了一下，初学，不明白为什么要借助随机优先值来修正，而这题本身自带优先值，为什么不能用这个来修正呢，给出的回答是：为了保证平衡，因为键值生成的BST树有很多种形态，需要另外一个key来保证二叉树的形态，而固定的函数在某些特殊情况下可能会不平衡，所以随机值比较靠谱。题目中所给的优先级不能保证树的形态，随机数辅助性的修正树的形态。还是有点不明白，先来个题解以后回过来应该更好理解了吧。

当然，这题典型用treap树做，但set、map、SBT、splay都可以的。下面给出Treap和set的方法，set这个相比要更简单，但treap有着set不可比拟的优势！

Treap

struct node

{

    node *ch[2];

    int r,k,p;

    node(int kk,int pp)

    {

        r=rand();

        k=kk,p=pp;

        ch[0]=ch[1]=NULL;

    }

    int cmp(int x)

    {

        if(x==p) return -1;

        return x<p?0:1;

    }

};

int find(node *root,int d)

{

    while(root->ch[d])

    {

        root=root->ch[d];

    }

    printf("%d\n",root->k);

    return root->p;

}

void rotate(node *&root,int d)

{

    node *tmp=root->ch[d^1];

    root->ch[d^1]=tmp->ch[d];

    tmp->ch[d]=root;

    root=tmp;

}

void insert(node *&root,int k,int p)

{

    if(root==NULL) root=new node(k,p);

    else

    {

        int d=p < root->p?0:1;

        insert(root->ch[d],k,p);

        if(root->ch[d]->r > root->r)//破坏了树的形态

            rotate(root,d^1);

    }

}

void remove(node *&root,int v)

{

    int d=root->cmp(v);

    if(d==-1)

    {

        node *tmp=root;

        if(root->ch[1]&&root->ch[0])

        {

            int d2=root->ch[1]->r < root->ch[0]->r?1:0;

            rotate(root,d2);//哪边小就往哪边旋转

            remove(root->ch[d2],v);

        }

        else

        {

            if(root->ch[0]==NULL) root=root->ch[1];

            else root=root->ch[0];

            delete tmp;//记得删除节点；

        }

    }

    else remove(root->ch[d],v);

}

int main()

{

    int n;

    node *root=NULL;

    while(~scanf("%d",&n)&&n)

    {

        if(n==1)

        {

            int k,p;

            scanf("%d%d",&k,&p);

            insert(root,k,p);

        }

        else

        {

            if(root==NULL) printf("0\n");

            else

            {

                int d=(n==2)?1:0;

                int v=find(root,d);

                remove(root,v);

            }

        }

    }

    return 0;

}

set

struct p

{

    int r,k;

    bool operator <(const p& tmp)const//自定义优先级

    {return r<tmp.r;}

};

set<p>q;

int main()

{

    q.clear();

     int n;

     while(~scanf("%d",&n)&&n)

     {

         if(n==1)

         {

             int k,r;

             scanf("%d%d",&k,&r);

             p tmp=(p){r, k};

             q.insert(tmp);

         }

         else

         {

             if(q.size()==0) printf("0\n");

             else

             {

                 set<p>::iterator it;

                 if(n==2) it=--q.end();

                 else it=q.begin();

                 printf("%d\n",it->k);

                 q.erase(it);

             }

         }

     }

     return 0;

}

边学边做，越学发现自己不会的越多，但至少自己是在进步，加油！

巴特西

POJ-3481 Double Queue,Treap树和set花式水过！

最新文章

热门文章