学步园

//在做这一题的时候，我刚开始是用STL中的set容器来做，很快就得到了答案，但提交上去就超时！
//再分析一下set中的数据结构，原来是红黑树，要的时间复杂度是O（n），所以就需要寻找一个时间
//复杂度更小的，所以只有堆了（二叉树），其时间复杂度为O（logn）!但当我用堆来完成的时候，由于
//使用了c++的输入输出方法，即cin和cout，又超时了！只有再换回c语言中的scanf和printf才解决问题
//（确实，c语言的scanf和printf的输入和输出确实要比c++中的cin和cout要快上4--5倍，因为c++的要涉及到一些对象问题！）
#include "iostream"
#include "cstring"
#include "algorithm"
#include "cstdio"
using namespace std;

void insert_min_heap(int pos);//往最小堆中插入元素
void insert_max_heap(int pos);//往最大堆中插入元素
void is_min_heap(int pos, int parent);//对最小堆的调整
void is_max_heap(int pos, int parent);//对最大堆的调整

struct Info
{
	//string name;
	char name[20];
	int SolveNum;
}max_heap[100010], min_heap[100010];



int main()
{
	char command[10];
	Info temp;
	int TestCase;
	//cin >> TestCase;
	scanf("%d", &TestCase);
	int tag = 0;//用于输出格式的判断位
	while (TestCase--)
	{
		if (tag != 0)
			//cout << endl;
			printf_s("\n");
		tag++;
		bool is_odd = true;//用于判断是奇数还是偶数
		int min_length = 0, max_length = 0;
		//string command;
		//while (cin >> command && command != "End")
		while (scanf("%s", command) && strcmp(command, "End") != 0)
		{
			//if (command == "Add")
			if (strcmp(command, "Add") == 0)
			{
				//cin >> temp.name  >> temp.SolveNum;
				scanf("%s", temp.name);
				scanf("%d", &temp.SolveNum);
				if (is_odd)//如果是奇数就插入最小堆中
				{
					min_length++;
					min_heap[min_length] = temp;
					insert_min_heap(min_length);
					is_odd = false;
				}
				else//如果是偶数就插入最大堆中
				{
					max_length++;
					max_heap[max_length] = temp;
					insert_max_heap(max_length);
					is_odd = true;
				}
				//如果最大堆的父节点的数大于最小堆父节点的数，就交换两个数，再对最大堆和最小堆进行调整
				if (max_length > 0 && min_length > 0 && max_heap[1].SolveNum > min_heap[1].SolveNum)
				{
					swap(max_heap[1], min_heap[1]);
					is_min_heap(min_length, 1);//对最大堆的调整
					is_max_heap(max_length, 1);//对最小堆的调整
				}
			}
		   // if (command == "Query")
			if (strcmp(command, "Query") == 0)
			{
				if (is_odd)
					//cout << min_heap[1].name << endl;
					printf("No one!\n");
				else
					//cout << "No one!" << endl;
					printf("%s\n", min_heap[1].name);
			}
		}
		if (is_odd)
		//cout << min_heap[1].name << " is so poor." << endl;
		printf("Happy BG meeting!!\n");
	else
		//cout << "Happy BG meeting!!" << endl;
		printf("%s is so poor.\n", min_heap[1].name);
	}	
}

void insert_min_heap(int pos)
{
	if (pos == 1)
		return;
	int parent = pos / 2;//得到父节点
	if (min_heap[parent].SolveNum > min_heap[pos].SolveNum)
	{
		swap(min_heap[parent], min_heap[pos]);
		insert_min_heap(parent);
	}
}

void insert_max_heap(int pos)
{
	if (pos == 1)
		return;
	int parent = pos / 2;
	if (max_heap[parent].SolveNum < max_heap[pos].SolveNum)
	{
		swap(max_heap[parent], max_heap[pos]);
		insert_max_heap(parent);
	}
}

void is_min_heap(int pos, int parent)
{
	int left, right;
	int min;
	left = parent * 2;
	right = parent * 2 + 1;

	if (left <= pos && min_heap[parent].SolveNum > min_heap[left].SolveNum)
		min = left;
	else
		min = parent;

	if (right <= pos && min_heap[min].SolveNum > min_heap[right].SolveNum)
		min = right;

	if (min != parent)
	{
		swap(min_heap[min], min_heap[parent]);
		is_min_heap(pos, min);
	}
}

void is_max_heap(int pos, int parent)
{
	int left, right;
	int max;
	left = parent * 2;
	right = parent * 2 + 1;

	if (left <= pos && max_heap[left].SolveNum > max_heap[parent].SolveNum)
		max = left;
	else
		max = parent;

	if (right <= pos && max_heap[right].SolveNum > max_heap[max].SolveNum)
		max = right;

	if (max != parent)
	{
		swap(max_heap[max], max_heap[parent]);
		is_max_heap(pos, max);
	}
}


//下面的代码是我使用set容器来做的，不过超时了！
//#include "iostream"
//#include "set"
//#include "string"
//using namespace std;
//
//struct Info
//{
//	string name;
//	int num;
//	bool operator < (const Info &a) const//重载<操作符，使排列从小到大
//	{
//		return a.num < num;
//	}
//};
//
//int main()
//{
//	int TestCase;
//	cin >> TestCase;
//	int tag = 0;
//	while (TestCase--)
//	{
//		if (tag != 0)
//			cout << endl;
//		tag++;
//		string str;
//		Info Input;
//		set<Info> s;
//		set<Info>::iterator it;
//		while (cin >> str && str != "End")
//		{
//			if (str == "Add")
//			{
//				cin >> Input.name >> Input.num;
//				s.insert(Input);
//			}
//			else if (str == "Query")
//			{
//				int size = s.size();
//				if (size % 2 == 0)
//					cout << "No one!" << endl;
//				else
//				{
//					int i;
//					for (i = 0, it = s.begin(); it != s.end(); it++, i++)
//						if (i == size/2)
//							cout << it->name << endl;
//				}
//			}
//		}
//		int num = s.size();
//		if (num % 2 == 0)
//			cout << "Happy BG meeting!!" << endl;
//		else 
//		{
//			int i;
//					for (i = 0, it = s.begin(); it != s.end(); it++, i++)
//						if (i == num/2)
//							cout << it->name << " is so poor." <<endl;
//		}
//	}
//}