hdu 1434 幸福列车 (Leftist Tree)

Problem - 1434

　　网上题解是普通的堆合并，都是用优先队列直接做的。可是正解的堆合并应该是用左偏堆或者斐波那契堆的吧，不然O(X * N ^ 2)的复杂度应该是过不了的。斐波那契堆的实现相对麻烦，所以我用了左偏堆完成这题，最坏复杂度O(X * N log N)。

　　这题就是一个模拟，没什么可以解释的。1y~

代码如下：

 #include <cstdio>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #include <string>

 using namespace std;

 template<class T>

 struct Node {

     int d;

     T dt;

     Node *l, *r;

     Node() { l = r = NULL;}

     Node(T dt) : dt(dt), d() { l = r = NULL;}

 } ;

 template<class T>

 Node<T> *merge(Node<T> *a, Node<T> *b) {

     if (!a) return b;

     if (!b) return a;

     if (a->dt < b->dt) return merge(b, a);

     a->r = merge(a->r, b);

     a->d = a->r ? a->r->d +  : ;

     return a;

 }

 template<class T>

 Node<T> *popTop(Node<T> *x) { Node<T> *ret = merge(x->l, x->r); delete x; return ret;}

 template<class T>

 struct Leftist {

     Node<T> *rt;

     void clear() { rt = NULL;}

     T top() { return rt->dt;}

     void push(T dt) { rt = merge(rt, new Node<T>(dt));}

     void pop() { rt = popTop(rt);}

 } ;

 const int N = ;

 typedef pair<int, string> PIS;

 Leftist<PIS> pq[N];

 char buf[];

 int main() {

     int n, m;

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

         int k, x, y;

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

             pq[i].clear();

             scanf("%d", &k);

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

                 scanf("%s%d", buf, &x);

                 pq[i].push(PIS(-x, buf));

             }

         }

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

             scanf("%s%d", buf, &x);

             if (!strcmp(buf, "GETOUT")) {

                 puts(pq[x].top().second.c_str());

                 pq[x].pop();

             }

             if (!strcmp(buf, "JOIN")) {

                 scanf("%d", &y);

                 pq[x].rt = merge(pq[x].rt, pq[y].rt);

                 pq[y].rt = NULL;

             }

             if (!strcmp(buf, "GETON")) {

                 scanf("%s%d", buf, &y);

                 pq[x].push(PIS(-y, buf));

             }

         }

     }

     return ;

 }

——written by Lyon