Untitled

#include <iostream>

using namespace std;
const int MAX_NODE = 18000;
const int HASH_SIZE = 30000;
struct Node{
	Node* parent;
	Node* child[3];
	int num;
	bool valid;
}NodePool[MAX_NODE];
int PoolCnt, GroupCnt;
struct HashNode{
	int key;
	Node* data;
}HashTbl[HASH_SIZE];


void hashAdd(int key, Node* data){
	unsigned long h = key % HASH_SIZE;
	while (HashTbl[h].key != 0)
	{
		if(HashTbl[h].key == key){
			HashTbl[h].data = data;
			return;
		}
		h = (h + 1) % HASH_SIZE;
	}
	HashTbl[h].key = key;
	HashTbl[h].data = data;
}

Node* hashFind(int key){
	unsigned long h = key % HASH_SIZE;
	int cnt = HASH_SIZE;
	while (HashTbl[h].key != 0 && cnt--)
	{
		if(HashTbl[h].key == key){
			return HashTbl[h].data;
		}
		h = (h + 1) % HASH_SIZE;
	}
	return nullptr;
}

void delNode(Node* node){
	if(node == nullptr)return;
	node->valid = false;
	for(int i = 0; i < 3; ++i){
		delNode(node->child[i]);
	}
}

void init(int N, int mId[], int nNum[]){
	PoolCnt = 0;
	for(int i = 0; i < HASH_SIZE; ++i){
		HashTbl[i].key = 0;
	}
	GroupCnt = N;
	for(int i = 0; i < N; ++i){
		Node* node = &NodePool[PoolCnt++];
		hashAdd(mId[i], node);
		node->valid = true;
		node->parent = nullptr;
		node->child[0] = node->child[1] = node->child[2] = nullptr;
		node->num = nNum[i];
	}
}

int add(int mId, int nNum, int mParent){
	Node* node = &NodePool[PoolCnt++];
	Node* parent = hashFind(mParent);
	if(parent->child[0] == nullptr){
		parent->child[0] = node;
	}
	else if(parent->child[1] == nullptr){
		parent->child[1] = node;
	}
	else if(parent->child[2] == nullptr){
		parent->child[2] = node;
	}
	else{
		return -1;
	}
	Node* curr = parent;
	while (curr)
	{
		curr->num += nNum;
		curr = curr->parent;
	}
	hashAdd(mId, node);
	node->valid = true;
	node->parent = parent;
	node->child[0] = node->child[1] = node->child[2] = nullptr;
	node->num = nNum;
	return parent->num;
}

int remove(int mId){
	Node* node = hashFind(mId);
	if(node == nullptr || node->valid == false){
		return -1;
	}
	Node* parent = node->parent;
	if(parent->child[0] == node){
		parent->child[0] = nullptr;
	}
	else if(parent->child[1] == node){
		parent->child[1] = nullptr;
	}
	else if(parent->child[2] == node){
		parent->child[2] = nullptr;
	}
	Node* curr = parent;
	while (curr)
	{
		curr->num-=node->num;
		curr = curr->parent;
	}
	delNode(node);
	return node->num;
}

int distribute(int K){
	int low = 1, high = 0;
	for(int i = 0; i < GroupCnt; ++i){
		if(NodePool[i].num > high){
			high = NodePool[i].num;
		}
	};
	while (low <= high)
	{
		int mid = (low + high)/2;
		int sum = 0;
		for(int i = 0; i < GroupCnt; ++i){
			if(NodePool[i].num <= mid){
				sum += NodePool[i].num;
			}
			else{
				sum += mid;
			}
		}
		if(sum <= K){
			low = mid + 1;
		}
		else{
			high = mid - 1;
		}
	}
	return high;
}

int main(){
	int mId[] = {7, 4, 2};
	int mNum[] = {25, 5, 40};
	init(3, mId, mNum);
	std::cout << add(3, 5, 4) << endl;//10
	std::cout << add(9, 5, 7) << endl;//30
	std::cout << add(1, 15, 4) << endl;//25
	std::cout << add(8, 10, 1) << endl;//25
	std::cout << distribute(100) << endl;//35
	std::cout << add(6, 20, 4) << endl;//55
	std::cout << distribute(109) << endl;//39
	std::cout << add(5, 20, 9) << endl;//25
	std::cout << distribute(131) << endl;//45
	std::cout << remove(1) << endl;//25
	std::cout << distribute(110) << endl;//40

	init(3, mId, mNum);
	

	return 0;
}