[Zerojudge]a091: 今晚打老虎

這題使用Deap就可以求解了。

P.S. 一個奇怪的問題是：同樣宣告int deap[1000005];，C++會說爆了(RE)，C卻不會= ="

[C](453ms, 1MB)

	#include<stdio.h>
	#include<stdlib.h>
	int deap[1000005];
	int length = 1;
	int isMaxHeap( int position )
	{
	while( position > 3 )
	position /= 2;
	return (position == 3);
	}
	int maxPartner( int position )
	{
	/* maxPartner = position + 2^([lg(position)] - 1) */
	if( position == 2 )
	return 2;
	int result = position, temp = 1;
	while( position > 3 )
	{
	position /= 2;
	temp *= 2;
	}
	result += temp;
	if( result > length ) return result / 2;
	return result;
	}
	int minPartner( int position )
	{
	/* minPartner = position - 2^([lg(position)] - 1) */
	int result = position, temp = 1;
	while( position > 3 )
	{
	position /= 2;
	temp *= 2;
	}
	result -= temp;
	return result;
	}
	void maxInsert( int position, int value )
	{
	int up = position/2, down = position;
	while( down > 3 && deap[up] < value )
	{
	deap[down] = deap[up];
	down = up;
	up = down/2;
	}
	deap[down] = value;
	}
	void minInsert( int position, int value )
	{
	int up = position/2, down = position;
	while( down > 2 && deap[up] > value )
	{
	deap[down] = deap[up];
	down = up;
	up = down/2;
	}
	deap[down] = value;
	}
	void insert( int value )
	{
	length++;
	if( length == 2 )
	{
	deap[length] = value;
	return;
	}
	else
	{
	int partner;
	if( isMaxHeap(length) )
	{
	partner = minPartner( length );
	if( value < deap[partner] )
	{
	deap[length] = deap[partner];
	minInsert( partner, value );
	}
	else
	maxInsert( length, value );
	}
	else
	{
	partner = maxPartner( length );
	if( value > deap[partner] )
	{
	deap[length] = deap[partner];
	maxInsert( partner, value );
	}
	else
	minInsert( length, value );
	}
	}
	}
	int maxDelete()
	{
	int deap_max = deap[3];
	int deap_last = deap[length--];
	int i, j;
	for( i = 3, j ; 2*i <= length ; i = j )
	{
	if( 2*i+1 <= length )
	j = ( deap[2*i] > deap[2*i+1] )? 2*i : 2*i+1;
	else
	j = 2*i;
	deap[i] = deap[j];
	}
	int partner = minPartner(i);
	if( 2*partner <= length )
	{
	if( 2*partner+1 <= length && deap[2*partner] < deap[2*partner+1] )
	partner = 2*partner+1;
	else
	partner = 2*partner;
	}
	if( deap_last < deap[partner] )
	{
	deap[i] = deap[partner];
	minInsert( partner, deap_last );
	}
	else
	maxInsert( i, deap_last );
	return deap_max;
	}
	int minDelete()
	{
	int deap_min = deap[2];
	int deap_last = deap[length--];
	int i, j;
	for( i = 2, j ; 2*i <= length ; i = j )
	{
	if( 2*i+1 <= length )
	j = ( deap[2*i] < deap[2*i+1] )? 2*i : 2*i+1;
	else
	j = 2*i;
	deap[i] = deap[j];
	}
	int partner = maxPartner(i);
	if( deap_last > deap[partner] )
	{
	deap[i] = deap[partner];
	maxInsert( partner, deap_last );
	}
	else
	minInsert( i, deap_last );
	return deap_min;
	}
	int main()
	{
	int control, value;
	while( scanf( "%d", &control ) != EOF )
	{
	switch( control )
	{
	case 1:
	scanf( "%d", &value );
	insert(value);
	break;
	case 2:
	if( length == 2 )
	printf( "%d\n", minDelete() );
	else
	printf( "%d\n", maxDelete() );
	break;
	case 3:
	printf( "%d\n", minDelete() );
	break;
	}
	}
	return 0;
	}

view raw Zerojudgea091.cpp hosted with ❤ by GitHub