题意：一开始有N只猴子,，每只都有一个力量值.，并且互不认识，，后来 它们之间发生了M次斗争。 每次两次两只猴子a，b斗争是， a和 b都会从他们自己的朋友圈里拉出一个最强的朋友， 之后最强的这两只猴子打， 打完后两只猴子的力量值分别减半.。并且 两只猴子的朋友圈的所有人都互相认识(也就是以后不会再打了)。问题是对于每次斗争, 若a，b是朋友, 那么输出-1， 否则输出斗争后它们的朋友圈里最强猴子的力量值。
分析：要表示集合的合并查找操作就是并查集最好了；要维护每次的最大值，就可以使用大顶堆，但还要方便的进行堆之间的合并操作，采用左偏树是最好的。该題也相当于左偏树的练习题了。
#include<iostream>using namespace std;#define N 100005class CLeftistTree{private:struct Set//并查集{int m_iParent; //父节点int m_iTreeRoot; //指向左偏树的根节点};struct Node//左偏树节点{int m_iLeft; //左子树int m_iRight; //右子树int m_iValue; //键值int m_iDis;//距离};public:CLeftistTree(){}~CLeftistTree(){}void ReadValue(int n);int Process(int a,int b);private:int FindRoot(int x);void UnionSet(int a,int b,int p);int MergeTree(int a,int b);Set m_sSet[N];Node m_sNode[N];};int CLeftistTree::MergeTree(int a,int b){if(a==0) return b;if(b==0) return a;if(m_sNode[a].m_iValue<m_sNode[b].m_iValue)swap(a,b);//值大的作为根节点（相当于大顶堆）m_sNode[a].m_iRight=MergeTree(m_sNode[a].m_iRight,b); //合并到右子树if(m_sNode[m_sNode[a].m_iLeft].m_iDis<m_sNode[m_sNode[a].m_iRight].m_iDis) //确保是一颗左偏树swap(m_sNode[a].m_iLeft,m_sNode[a].m_iRight);if(m_sNode[a].m_iRight==0) m_sNode[a].m_iDis=0; //更新距离elsem_sNode[a].m_iDis=m_sNode[m_sNode[a].m_iRight].m_iDis+1;return a;}void CLeftistTree::UnionSet(int a,int b,int p){if(a<b){m_sSet[a].m_iParent=b;m_sSet[b].m_iTreeRoot=p;}else{m_sSet[b].m_iParent=a;m_sSet[a].m_iTreeRoot=p;}}int CLeftistTree::FindRoot(int x){int root=x;int parent;while(root!=m_sSet[root].m_iParent) root=m_sSet[root].m_iParent;parent=m_sSet[x].m_iParent;while(parent!=root) //路径压缩{m_sSet[x].m_iParent=root;x=parent;parent=m_sSet[x].m_iParent;}return root;}int CLeftistTree::Process(int a,int b){int x,y,p,q;if(FindRoot(a)==FindRoot(b)) //在同一个集合中return -1;x=m_sSet[FindRoot(a)].m_iTreeRoot; //找到左偏树的根y=m_sSet[FindRoot(b)].m_iTreeRoot;p=MergeTree(m_sNode[x].m_iLeft,m_sNode[x].m_iRight); //取出根，合并左右子树到左偏树q=MergeTree(m_sNode[y].m_iLeft,m_sNode[y].m_iRight);m_sNode[x].m_iValue/=2;m_sNode[x].m_iDis=m_sNode[x].m_iLeft=m_sNode[x].m_iRight=0; //两个最大猴子的值减半m_sNode[y].m_iValue/=2;m_sNode[y].m_iDis=m_sNode[y].m_iLeft=m_sNode[y].m_iRight=0;p=MergeTree(p,x); //分别插入原来的树中q=MergeTree(q,y);p=MergeTree(p,q); //得到一棵完整的树UnionSet(FindRoot(a),FindRoot(b),p);//并查集合并return m_sNode[p].m_iValue;}void CLeftistTree::ReadValue(int n){int i;for(i=1;i<=n;i++){scanf("%d",&m_sNode[i].m_iValue);m_sNode[i].m_iDis=m_sNode[i].m_iLeft=m_sNode[i].m_iRight=0;m_sSet[i].m_iParent=i;m_sSet[i].m_iTreeRoot=i;}}CLeftistTree left_tree;int main(){int n,M,x,y;while(scanf("%d",&n)==1){left_tree.ReadValue(n);scanf("%d",&M);while(M–){scanf("%d %d",&x,&y);printf("%d\n",left_tree.Process(x,y));}}return 0;}
去陌生的街角，去做一切我们曾经或现在也很想做的事情，
