HDU – 1512 Monkey King 【可並堆 思維】

NO IMAGE

傳送門
題目大意:有n個猴子,一開始每個猴子只認識自己。每個猴子有一個力量值,力量值越大表示這個猴子打架越厲害。如果2個猴子不認識,他們就會找他們認識的猴子中力量最大的出來單挑,單挑不論輸贏,單挑的2個猴子力量值減半,這2撥猴子就都認識了,不打不相識嘛。現在給m組詢問,如果2只猴子相互認識,輸出-1,否則他們各自找自己認識的最牛叉的猴子單挑,求挑完後這撥猴子力量最大值。

題目分析:首先很明顯這題涉及到集合並的操作,要用到並查集。其次要找到某一撥猴子中力量最大值,找最大值最快的應該是堆。2撥猴子要快速合併而又不失堆的特性,所以很明顯的可並堆, 注意最大值那的處理!

注意新的最大值的處理… 細節請看程式碼.

AC Code

const int maxn = 1e5   5;
int root[maxn];
struct Ltree {
int ls[maxn], rs[maxn];
ll val[maxn];
void cc() {
Fill(ls, 0); Fill(rs, 0);
}
int Un(int x, int y){
if (!x || !y) return x y;
if (val[x] < val[y]) swap(x,y);
rs[x] = Un(rs[x], y);
swap(ls[x], rs[x]);
root[ls[x]] = root[rs[x]] = x;
root[x] = x;
return x;
}
void pop(int &x) {
x = Un(ls[x], rs[x]);
}
int top(int x) {
return val[x];
}
}heap;
int n, m;
int Find(int x) {
return root[x] == x ? x : root[x] = Find(root[x]);
}
void solve() {
while(~scanf("%d", &n)) {
heap.cc();
for (int i = 1 ; i <= n ; i   ) {
ll x; scanf("%lld", &x);
heap.val[i] = x;
root[i] = i;
}
scanf("%d", &m);
while(m --) {
int u, v;
scanf("%d%d", &u, &v);
int fu = Find(u), fv = Find(v);
if (fu == fv) puts("-1");
else {
heap.val[fu] >>= 1;
heap.val[fv] >>= 1;
heap.pop(root[u]); heap.pop(root[v]);
heap.ls[fu] = heap.rs[fu] = 0;
heap.ls[fv] = heap.rs[fv] = 0;
root[u] = heap.Un(fu, root[u]);
root[v] = heap.Un(fv, root[v]);
root[u] = heap.Un(root[u], root[v]);
printf("%d\n", heap.val[root[u]]);
}
}
}
}