c.cpp

ACM大赛基本练习题

#include<stdio.h>
#include<stdlib.h>

#define SIZE 1048576

typedef struct Node Node;

struct Node
{
	int pos;
	int size;
	int used;
	Node *left;
	Node *right;
};

Node *getNode( int pos, int size )
{
	Node *nod = ( Node * ) malloc( sizeof( Node ) );
	nod->left = NULL;
	nod->right = NULL;
	nod->pos = pos;
	nod->size = size;
	nod->used = 0;

	return nod;
}

int insert( Node *nod, int size )
{
	int half = nod->size / 2;

	if( nod->used || size > nod->size )
		return 0;

	if( size > half )
	{
		if( nod->left == NULL )
		{
			nod->used = 1;
			return 1;
		}
		else
			return 0;
	}

	if( nod->left == NULL )
		nod->left = getNode( nod->pos, half );

	if( insert( nod->left, size ) )
		return 1;
	else
	{
		if( nod->right == NULL )
			nod->right = getNode( nod->pos + half, half );
		
		if( insert( nod->right, size ) )
		{
			if( nod->left->used && nod->right->used )
				nod->used = 1;
			return 1;
		}
		else
			return 0;
	}
}

void clear_it( Node *nod )
{
	if( !nod )
		return;
	clear_it( nod->left );
	clear_it( nod->right );
	free( nod );
}

void make_it()
{
	int i;
	int num;
	int nowSize;
	int count;

	Node *head = getNode( 0, SIZE );
	
	scanf( "%d", &num );

	count = 0;
	
	for( i = 0; i < num; ++i )
	{
		scanf( "%d", &nowSize );
		if( insert( head, nowSize ) )
			++count;
	}
	
	printf( "%d\n", count );

	clear_it( head );
}

int main()
{
	int dataCase, i;

	scanf( "%d", &dataCase );

	for( i = 0; i < dataCase; ++i )
		make_it();

	return 0;
}