程序员人生网站导航

BZOJ 1455 罗马游戏可并堆

栏目：php教程时间：2015-03-17 08:30:43

题目大意

给出n个人的权值，每次要求将两队人合成1堆，或杀掉1堆人中的权值最小的那个人。问每次删除的人的权值是多少。

思路

就是可并堆，没了。我挑最简单的随机堆写的。

CODE

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define MAX 1000010
using namespace std;

struct Heap{
    Heap *son[2];
    int val;

    Heap(int _):val(_) {
        son[0] = son[1] = NULL;
    }
    Heap() {}
}*heap[MAX],mempool[MAX],*C = mempool + 1;

Heap *Merge(Heap *x,Heap *y)
{
    if(x == NULL)   return y;
    if(y == NULL)   return x;
    if(x->val > y->val)    swap(x,y);
    bool k = rand()&1;
    x->son[k] = Merge(x->son[k],y);
    return x;
}

int points,asks;
int src[MAX];
bool killed[MAX];
char s[10];

int father[MAX];

int Find(int x)
{
    if(father[x] == x)  return x;
    return father[x] = Find(father[x]);
}

int main()
{
    srand(19970806);
    cin >> points;
    for(int i = 1; i <= points; ++i)
        father[i] = i;
    for(int x,i = 1; i <= points; ++i) {
        scanf("%d",&x);
        heap[i] = new (C++)Heap(x);
    }
    cin >> asks;
    for(int x,y,i = 1; i <= asks; ++i) {
        scanf("%s",s);
        if(s[0] == 'M') {
            scanf("%d%d",&x,&y);
            if(killed[x] || killed[y])  continue;
            int fx = Find(x),fy = Find(y);
            if(fx == fy)    continue;
            father[fy] = fx;
            heap[fx] = Merge(heap[fx],heap[fy]);
        }
        else {
            scanf("%d",&x);
            if(killed[x]) {
                puts("0");
                continue;
            }
            int fx = Find(x);
            printf("%d
",heap[fx]->val);
            killed[heap[fx] - mempool] = true;
            heap[fx] = Merge(heap[fx]->son[0],heap[fx]->son[1]);
        }
    }
    return 0;
}

------分隔线----------------------------

上一篇 数学之路-sas备忘(9)

下一篇 [LeetCode] 021. Merge Two Sorted Lists (Easy) (C++/Python)

------分隔线----------------------------