Untitled
unknown
plain_text
3 years ago
6.9 kB
8
Indexable
#include <iostream> #include <vector> #pragma warning(suppress : 4996) using namespace std; struct Node { int key; int height; Node* left; Node* right; }; Node* CreateNode(int x) { Node* temp = new Node; temp->key = x; temp->left = temp->right = nullptr; temp->height = 1; return temp; } int getHeight(Node* t) { if (t == nullptr) return 0; return t->height; } Node* rightRotate(Node* y) { Node* x = y->left; Node* T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->height = max(getHeight(y->left),getHeight(y->right)) + 1; x->height = max(getHeight(x->left),getHeight(x->right)) + 1; // Return new root return x; } // A utility function to left // rotate subtree rooted with x // See the diagram given above. Node* leftRotate(Node* x) { Node* y = x->right; Node* T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(getHeight(x->left), getHeight(x->right)) + 1; y->height = max(getHeight(y->left), getHeight(y->right)) + 1; // Return new root return y; } // Get Balance factor of node N int getBalance(Node* N) { if (N == NULL) return 0; return getHeight(N->left) - getHeight(N->right); } Node* insert(Node* node, int key) { /* 1. Perform the normal BST insertion */ if (node == NULL) return(CreateNode(key)); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys are not allowed in BST node->left = insert(node->left, key); /* 2. Update height of this ancestor node */ node->height = 1 + max(getHeight(node->left), getHeight(node->right)); /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */ int balance = getBalance(node); // If this node becomes unbalanced, then // there are 4 cases // Left Left Case if (balance > 1 && key < node->left->key) return rightRotate(node); // Right Right Case if (balance < -1 && key > node->right->key) return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left Case if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node; } Node* minValueNode(Node* node) { Node* current = node; /* loop down to find the leftmost leaf */ while (current->left != NULL) current = current->left; return current; } Node* deleteNode(Node* root, int key) { // STEP 1: PERFORM STANDARD BST DELETE if (root == NULL) return root; // If the key to be deleted is smaller // than the root's key, then it lies // in left subtree if (key < root->key) root->left = deleteNode(root->left, key); // If the key to be deleted is greater // than the root's key, then it lies // in right subtree else if (key > root->key) root->right = deleteNode(root->right, key); // if key is same as root's key, then // This is the node to be deleted else { // node with only one child or no child if ((root->left == NULL) || (root->right == NULL)) { Node* temp = root->left ? root->left : root->right; // No child case if (temp == NULL) { temp = root; root = NULL; } else // One child case *root = *temp; // Copy the contents of // the non-empty child free(temp); } else { // node with two children: Get the inorder // successor (smallest in the right subtree) Node* temp = minValueNode(root->right); // Copy the inorder successor's // data to this node root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } } // If the tree had only one node // then return if (root == NULL) return root; // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE root->height = 1 + max(getHeight(root->left),getHeight(root->right)); // STEP 3: GET THE BALANCE FACTOR OF // THIS NODE (to check whether this // node became unbalanced) int balance = getBalance(root); // If this node becomes unbalanced, // then there are 4 cases // Left Left Case if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Left Right Case if (balance > 1 && getBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } // Right Right Case if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root); // Right Left Case if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } int findMax(Node* t) { if (t->right == nullptr) return t->key; return findMax(t->right); } int findBMax(Node* t) { if (t->right == nullptr) { if (t->left == nullptr) return t->key; else return t->left->key; } if (t->right->right == nullptr) return t->key; return findBMax(t->right); } long long chiPhi(int N,int K, vector<int> type, Node* head) { long long res = 0,temp; for (int i = 0; i < K; i++) { if (type[i] == 1) { temp = findMax(head); res += temp; head = deleteNode(head, temp); } else { temp = findBMax(head); res += temp; head = deleteNode(head, temp); } } return res; } #pragma warning(disable : 4996) int main() { int N, K; cin >> N; Node* head = nullptr; vector<int> price(N); for (int i = 0; i < N; ++i) { cin >> price[i]; head = insert(head, price[i]); } cin >> K; vector<int> type(K); for (int i = 0; i < K; ++i) cin >> type[i]; cout << chiPhi(N,K,type,head); return 0; }
Editor is loading...