2239.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

#include <stdio.h>
#include <memory.h>
#include <algorithm>

struct node
{
	int ax;
	int kx;
	int id;
}nd[50001];

int id[50000],n;
int min[50000];

const int MAX_VALUE = 1000000000;

int get_min_spec( int l, int r )
{
	if( l > r ) return MAX_VALUE;
	else return min[ (l+r)/2 ];
}

void creat( int l, int r )
{
	if( l > r ) return;

	int c = (l+r)/2, temp;

	creat( l, c-1 );
	creat( c+1, r );

	min[c] = nd[c].ax;
	id[c] = c;

	if( ( temp = get_min_spec( l, c-1 ) ) < min[c] )
		min[c] = temp, id[c] = id[ (l+c-1)/2 ];
	if( ( temp = get_min_spec( c+1, r ) ) < min[c] )
		min[c] = temp, id[c] = id[ (r+c+1)/2 ];

}

// [a,b] is to be counted
int get_min( int l, int r , int a, int b , int &min_id )
{
	int c = ( l + r ) / 2;

	if( l > r || r < a || l > b ) 
	{
		min_id = -1;
		return MAX_VALUE;
	}
	
	if( a<=l && r <=b )
	{
		min_id = id[ c ];
		return min[ c ];
	}
	else
	{
		int id1, id2, v1, v2, v;
		v1 = get_min( l, c-1, a, b, id1 );
		v2 = get_min( c+1, r, a, b, id2 );

		if(  a <= c && c <= b )
			v = nd[c].ax, min_id = c;
		else v = MAX_VALUE, min_id = -2; 
		
		if( v1 < v ) v = v1, min_id = id1;
		if( v2 < v ) v = v2, min_id = id2;
		
		return v;
	}
	
	return MAX_VALUE;
}


bool cmp( node a, node b )
{
	return a.kx < b.kx;
}

int parent[50000],lchild[50000],rchild[50000];

void init()
{
	int i;

	scanf( "%d", &n );

	for( i=0; i<n; i++ )
	{
		scanf( "%d %d", &nd[i].kx, &nd[i].ax );
		nd[i].id = i;
	}

	std::sort( nd, nd+n, cmp );
	
	creat( 0, n-1 );
	nd[n].id = -1;

//	printf( "creat ok\n" );
//	printf( "%d %d\n", min[(0+n-1)/2], nd[ id[(n-1)/2] ].id + 1 );
}

int doit( int l, int r, int f )
{
	int root;

	if( l > r ) return n;

	get_min( 0, n-1, l, r, root );
	parent[ nd[root].id ] = f;

	lchild[ nd[root].id ] = doit( l, root-1, root );
	rchild[ nd[root].id ] = doit( root+1, r, root );

	return root;
}

int main()
{
	int i;
	init();
	
	printf( "YES\n" );
	
	doit( 0, n-1, n );

	for( i=0; i<n; i++ )
		printf( "%d %d %d\n", nd[parent[i]].id + 1, nd[lchild[i]].id + 1, nd[rchild[i]].id + 1 );
	
	return 0;
}