黑箱子，穿越千年的超时

码拜

10年 ago

有一个黑箱子，里面会按升序存储整数，你可以对黑箱子下达下面的指令：
a. ADD n 将n加入黑箱子
b. Get 获得一个数，这个数在黑箱子里的序号（从0开始计数）是Get的出现次数。
黑箱子中最初存了一个数0，现给你一个操作序列，要你输出Get命令时获的那个数。
输入：
每行是一个命令，假如命令是”ADD”，则后面空一格，有一个整数。输入时保证GET命令不会越界
输出：
每行输出一个整数，整数为对应Get获得值。

Sample Input
ADD 3
GET
ADD 1
GET
ADD -4
ADD 2
ADD 8
GET
GET
ADD -1000
ADD 2
GET

Sample Output
3
3
2
3
2

//Time limit Exceed
#include <stdio.h>
#include <stdlib.h>
#define N 1000000
int MinHeap[N],minsize;
int MaxHeap[N],maxsize=1;
int minHeapPop()
{
    //用temp保存被弹出的元素，val保存最后一个待调整元素，h找到val应放置的位置,child为孩子位置
    int temp=MinHeap[1],val,h,child;
    val=MinHeap[minsize--];
    for(h=1,child=2*h; child<=minsize&&(val>MinHeap[child]||val>MinHeap[child+1]) ;){
        if(MinHeap[child+1]<MinHeap[child]){
            child++;
        }
        MinHeap[h]=MinHeap[child];
        h=child,child=2*h;
    }
    MinHeap[h]=val;
    return temp;
}
int maxHeapPop()
{
    int temp=MaxHeap[1],val,h,child;
    val=MaxHeap[maxsize--];
    for(h=1,child=2*h; child<=maxsize&&(val<MaxHeap[child]||val<MaxHeap[child+1]) ;){
        if(MaxHeap[child+1]>MaxHeap[child]){
            child++;
        }
        MaxHeap[h]=MaxHeap[child];
        h=child,child=2*h;
    }
    MaxHeap[h]=val;
    return temp;
}
void minHeapInsert(int x)
{
    int h=++minsize,parent=h/2;
    while(h>1 && x<MinHeap[parent]){
        MinHeap[h]=MinHeap[parent];
        h=parent,parent=h/2;
    }
    MinHeap[h]=x;
}
void maxHeapInsert(int x)
{
    int h=++maxsize,parent=h/2;
    while(h>1 && x>MaxHeap[parent]){
        MaxHeap[h]=MaxHeap[parent];
        h=parent,parent=h/2;
    }
    MaxHeap[h]=x;
}
void blackBoxOpera()
{
    char cmd[5];
    int x;
    while(scanf("%s",cmd)){
        if(cmd[0]=="G"){//the MinHeap"s top element always is the answer
            printf("%d\n",MinHeap[1]);
            maxHeapInsert(minHeapPop());
        }
        else{
            scanf("%d",&x);
            if(x<MaxHeap[1]){//the MaxHeap"s top is next "GET" position
                minHeapInsert(maxHeapPop());
                maxHeapInsert(x);
            }
            else
                minHeapInsert(x);
        }//else
    }//while
}
int main()
{
    blackBoxOpera();
    return 0;
}

最开始用双向链表做的，以为可以。果断超时。花了些时间搞这个堆，还是不行吖？

解决方案

那就试试Splay Tree

不知道B树，行不？

B树可以吗？你可以试试吧，下面的代码可以参考下。

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
/* Balance flag */
#define RH 1
#define LH -1
#define BH 0
static int lev_m=0;
typedef struct avlNode{
	int data;
	int balance;
	int level;
	struct avlNode *right;
	struct avlNode *left;
}*PavlNode;
void lltree(PavlNode *node)
{
	PavlNode lnode;
	lnode = (*node)->left;
	(*node)->left = lnode->right;
	lnode->right = *node;
	*node=lnode;
}
void lrtree(PavlNode *node)
{
	PavlNode rnode,lnode;
	lnode = (*node)->left;
	rnode = lnode->right;
	(*node)->left = rnode;
	lnode->right =  rnode->left;
	rnode -> left = lnode;
	lltree(node);
}
void left_balance_tree(PavlNode *node)
{
	PavlNode rnode,lnode;
	lnode = (*node)->left;
	switch(lnode->balance){
		case LH:
			(*node)->balance = lnode->balance = BH;
			lltree(node);
			break;
		case RH:
			rnode = lnode->right;
			switch(rnode->balance){
				case BH:
					(*node)->balance = BH;
					lnode->balance = BH;
					break;
				case LH:
					(*node)->balance = RH;
					lnode->balance = BH;
					break;
				case RH:
					(*node)->balance = BH;
					lnode->balance = LH;
					break;
			}
			rnode->balance = BH;
			lrtree(node);
			break;
		defult:
			// do nothing
			break;
	}
}
void rrtree(PavlNode *node)
{
	PavlNode rnode;
	rnode = (*node)->right;
	(*node)->right = rnode->left;
	rnode->left = *node;
	*node=rnode;
}
void rltree(PavlNode *node)
{
	PavlNode rnode,lnode;
	rnode = (*node)->right;
	lnode = rnode->left;
	(*node)->right = rnode->left;
	rnode->left = lnode->right;
	lnode -> right = rnode;
	rrtree(node);
}
void right_balance_tree(PavlNode *node)
{
	PavlNode rnode,lnode;
	rnode = (*node)->right;
	switch(rnode->balance){
		case LH:
			lnode = rnode->left;
			switch(lnode->balance){
				case BH:
					(*node)->balance = BH;
					rnode->balance = BH;
					break;
				case LH:
					(*node)->balance = LH;
					rnode->balance = BH;
					break;
				case RH:
					(*node)->balance = BH;
					rnode->balance = RH;
					break;
				defult:
					break;
			}
			lnode->balance = BH;
			rltree(node);
			break;
		case RH:
			(*node)->balance = rnode->balance = BH;
			rrtree(node);
			break;
		default:
			break;
	}
}
int create_tree(PavlNode *node, int data,  int* taller){
	if((*node) == NULL){
		(*node) = malloc(sizeof(struct avlNode));
		(*node)->data = data;
		(*node)->balance = BH;
		(*node)->level = 0;
		(*node)->right = NULL;
		(*node)->left = NULL;
		return 1;
	}
	if( data <= (*node)->data ){
		if(!create_tree(&((*node)->left),data,taller)){
			return 0;
		}
		if(*taller){
			switch((*node)->balance){
				case BH:
					(*node)->balance = LH;
					*taller = 1;
					break;
				case LH:
					left_balance_tree(node);
					*taller = 0;
					break;
				case RH:
					(*node)->balance = BH;
					 *taller = 0;
					break;
				default:
					// do nothing
					break;
			}
		}
	}else{
		if(!create_tree(&((*node)->right),data,taller)){
			return 0;
		}
		if(*taller){
			switch((*node)->balance){
				case BH:
					(*node)->balance = RH;
					*taller = 1;
					break;
				case LH:
					(*node)->balance = BH;
					*taller = 0;
					break;
				case RH:
					right_balance_tree(node);
					*taller = 0;
					break;
				default:
					// do nothing
					break;
			}
		}
	}
	return 1;
}
void delete_tree(PavlNode* node){
	if((*node) == NULL){
		return;
	}
	if((*node)->right != NULL ){
		delete_tree(&((*node)->right));
	}
	if((*node)->left !=NULL ){
		delete_tree(&((*node)->left));
	}
	if(((*node)->right == NULL) && ((*node)->right == NULL)){
		free((*node));
		(*node) == NULL;
	}
	return;
}
int main(void)
{
	int tmp;
	int i,j;
	int taller;
	int lev_tmp=0;
	PavlNode root=NULL;
	srand((unsigned)time(NULL));
	for(i=0; i<50; i++){
		taller=1;
		tmp = rand()%100;
		create_tree(&root,tmp,&taller);
	}
	delete_tree(&root);
	return 0;
}