您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

ZOJ 2334 Monkey King 解題報告：左偏樹與並查集結合

編輯：關於C

題目大意

有 n 隻猴子，每隻有初始戰力。進行 m 次操作：指定兩隻猴子 a, b 決鬥。規則如下：

若兩猴子屬同一群體，輸出 -1
否則各群體最強猴子出戰，戰力減半（v = v/2）並重新歸隊
兩群體合併，輸出合併後最強猴子戰力

核心資料結構

左偏樹

可合併堆，支援 merge、insert、pop（刪除堆頂）皆為 O(log n)
維護距離 dist：右子樹距離 ≤ 左子樹距離，合併時若違反則交換左右子樹

並查集

維護群體關係，find 路徑壓縮
額外陣列 id[x] 記錄群體 x 對應的左偏樹根節點編號

關鍵演算法流程

初始化：
  每隻猴子自成一群，建立單節點左偏樹
  並查集 p[i] = i，id[i] = 對應樹節點

處理每次決鬥 (a, b)：
  x = find(a), y = find(b)
  if x == y: 輸出 -1
  else:
    // 取出兩群最強猴子
    u = top(id[x]); id[x] = pop(id[x]); id[x] = insert(id[x], u/2)
    u = top(id[y]); id[y] = pop(id[y]); id[y] = insert(id[y], u/2)
    // 合併群體與左偏樹
    p[x] = y
    id[y] = merge(id[x], id[y])
    輸出 top(id[y])

完整程式碼

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

const int maxn = 300000 + 10;
int v[maxn], l[maxn], r[maxn], d[maxn];
int p[maxn], id[maxn];
int tot;

int find_set(int x) {
    return p[x] == x ? x : p[x] = find_set(p[x]);
}

int merge(int x, int y) {
    if (!x) return y;
    if (!y) return x;
    if (v[x] < v[y]) swap(x, y);        // 大根堆
    r[x] = merge(r[x], y);
    if (d[l[x]] < d[r[x]]) swap(l[x], r[x]);
    d[x] = d[r[x]] + 1;
    return x;
}

int init_node(int val) {
    ++tot;
    v[tot] = val;
    l[tot] = r[tot] = d[tot] = 0;
    return tot;
}

int insert(int root, int val) {
    return merge(root, init_node(val));
}

int top(int root) { return v[root]; }

int pop(int root) { return merge(l[root], r[root]); }

int main() {
    int n, m, u, a, b;
    while (~scanf("%d", &n)) {
        tot = 0;
        for (int i = 1; i <= n; i++) {
            p[i] = i;
            id[i] = i;
        }
        for (int i = 1; i <= n; i++) {
            scanf("%d", &u);
            init_node(u);  // 節點編號即 i
        }
        scanf("%d", &m);
        while (m--) {
            scanf("%d%d", &a, &b);
            int x = find_set(a), y = find_set(b);
            if (x == y) {
                puts("-1");
            } else {
                int u = top(id[x]);
                id[x] = pop(id[x]);
                id[x] = insert(id[x], u / 2);

                u = top(id[y]);
                id[y] = pop(id[y]);
                id[y] = insert(id[y], u / 2);

                p[x] = y;
                id[y] = merge(id[x], id[y]);
                printf("%d\n", top(id[y]));
            }
        }
    }
    return 0;
}