您當前位置：首頁 > php開源 > php教程 > BZOJ 1455 羅馬游戲可并堆

BZOJ 1455 羅馬游戲可并堆

來源：程序員人生發布時間：2015-03-17 08:30:43 閱讀次數：3080次

題目大意

給出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;
}