P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G BST题解
P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
这是一道贪心算法的题目,用BST维护有序性,每次取最小值,并删除,取两次合并为新的一堆,进行n-1次,这样就合并为一堆了统计过程每一次的大小。
指针版
#includeusing namespace std; struct BSTNode{ int key; BSTNode* left; BSTNode* right; BSTNode* parent; BSTNode(long long value,BSTNode* p,BSTNode* l,BSTNode* r): key(value),parent(p),left(l),right(r){ } }; BSTNode* Search(BSTNode* root,int key) { if (root==NULL||root->key==key) { return root; } if (key key) { return Search(root->left,key); } else { return Search(root->right,key); } } BSTNode* Maximum(BSTNode* root) { if (root==NULL) { return root; } while(root->right!=NULL) { root=root->right; } return root; } BSTNode* Minimum(BSTNode* root) { if (root==NULL) { return root; } while(root->left!=NULL) { root=root->left; } return root; } BSTNode* Predecessor(BSTNode* root) { if (root->left!=NULL) { return Maximum(root->left); } BSTNode* y=root->parent; while(y!=NULL&&root==y->left) { root=y; y=y->parent; } return y; } BSTNode* Successor(BSTNode* root) { if(root->right!=NULL) { return Minimum(root->right); } BSTNode* y=root->parent; while(y!=NULL&&root==y->right) { root=y; y=y->parent; } return y; } void Insert(BSTNode* &root,int key) { BSTNode* z=NULL; if ((z=new BSTNode(key,NULL,NULL,NULL))==NULL) { return ; } BSTNode* y=NULL; BSTNode* x=root; while(x!=NULL) { y=x; if (z->key key) { x=x->left; } else { x=x->right; } } z->parent=y; if (y==NULL) { root=z; } else if(z->key key) { y->left=z; } else { y->right=z; } } void Remove(BSTNode* &root,int key) { BSTNode *z; z=Search(root,key); if (z!=NULL) { BSTNode* x=NULL; BSTNode* y=NULL; if (z->left==NULL||z->right==NULL) { y=z; } else { y=Successor(z); } if (y->left!=NULL) { x=y->left; } else { x=y->right; } if (x!=NULL) { x->parent=y->parent; } if (y->parent==NULL) { root=x; } else if(y==y->parent->left) { y->parent->left=x; } else { y->parent->right=x; } if (y!=z) { z->key=y->key; } delete y; } } int main() { int n,ans=0,cur; cin>>n; BSTNode* root=NULL; for (int i=1;i<=n;i++) { int x; cin>>x; Insert(root,x); } BSTNode* z1; BSTNode* z2; for (int i=1;i key; Remove(root,z1->key); z2=Minimum(root); cur+=z2->key; Remove(root,z2->key); ans+=cur; Insert(root,cur); } cout< 数组版
#includeusing namespace std; struct node{ int data;//结点的内容 int left;//左子树 int right;//右子树 int cnt; } Bst[20100]; int root=0; int tot=0; //插入x的值 void insert(int &r,int x) { if (r==0) { tot++; r=tot; Bst[tot].data=x; Bst[tot].left=0; Bst[tot].right=0; Bst[tot].cnt=1; } else { if(x>Bst[r].data) { insert(Bst[r].right,x); } else if(x val) { return Search(Bst[r].left,val); } else if(Bst[r].data==val) { return r; } else { return Search(Bst[r].right,val); } } //查询r子树的最小值的结点编号 int findMin(int r) { if (r==0) { return 0; } else { int ans=r; while(Bst[r].left!=0) { ans=Bst[r].left; r=Bst[r].left; } return ans; } } //查询r子树的最大值的结点编号 int findMax(int r) { if (r==0) { return 0; } else { int ans=r; while(Bst[r].right!=0) { ans=Bst[r].right; r=Bst[r].right; } return ans; } } //删除算法这个算法不是最好可以优化 void Delete(int &r,int val) { if (r==0) { return ; } else if(Bst[r].data==val) { if(Bst[r].left==0&&Bst[r].right==0) { r=0; return ; } else if(Bst[r].left==0) //仅有右子树 { int y,v; y=findMin(Bst[r].right);//右子树查最小值 v=Bst[y].data; Bst[r].data=v; Bst[r].cnt=Bst[y].cnt; Delete(Bst[r].right,v); } else if(Bst[r].right==0)//仅有左子树 { int y,v; y=findMax(Bst[r].left);//右子树查最大值 v=Bst[y].data; Bst[r].data=v; Bst[r].cnt=Bst[y].cnt; Delete(Bst[r].left,v); } else //有两个子树 { int y,v; y=findMin(Bst[r].right);//右子树查最小值 v=Bst[y].data; Bst[r].data=Bst[y].data; Bst[r].cnt=Bst[y].cnt; Delete(Bst[r].right,v); } } else if(Bst[r].data>val) { Delete(Bst[r].left,val); } else { Delete(Bst[r].right,val); } } void DElete(int r,int val) { int x; x=Search(r,val); Bst[x].cnt--; if (Bst[x].cnt==0) { Delete(r,val); } } int a[10010]; void build(int l,int r) { if (r-l<1) return ; int m; m=(l+r)/2; insert(root,a[m]); build(l,m); build(m+1,r); } int main() { //freopen("P1090_2.in","r",stdin); int n; cin>>n; for (int i=0;i >a[i]; } build(0,n); int ans=0; for (int i=1;i