#include<stdio.h>
#include<string.h>
#include<math.h>
const long map[ 26 ] = { 2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,0,7,7,8,8,8,9,9,9,0 };
const long MAX =  100000;
class Arrange {									// rearrange a array by alg : merge
public :
	Arrange( void );
	void Set_value( long , long, long );
	void Set_len( long );
	void Output( void );
	void Merge( long , long , long );
	void Merge_sort( long , long  );
private :
	long A[ MAX ];								// data
	long Num[ MAX ];							// the amount of data
	long len;
};
Arrange ::Arrange( void )
{
	long i;
	for ( i = 0; i < MAX; i ++ ) {
		A[ i ] = 100000000;
		Num[ MAX ] = 0;
	}
}
void Arrange ::Set_value( long a, long num, long i )
{
	A[ i ] = a;
	Num[ i ] = num;
}
void Arrange ::Set_len( long l )
{
	len = l;
}
void Arrange ::Output( )
{
	long i;
	for ( i = 1; i <= len; i ++ ) {
		printf( "%03ld-%04ld %ld\n", A[ i ] / 10000, A[ i ] % 10000 , Num[ i ] );
	}
}
void Arrange ::Merge( long p, long q, long r ) 
{
	long L[ MAX ];
	long L_num[ MAX ];
	long R[ MAX ];
	long R_num[ MAX ];
	long L_len;
	long R_len;
	long i;
	long j;
	long k;

	L_len = q - p + 1;
	R_len = r - q;
	for ( i = 1; i <= L_len; i ++ ) {
		L[ i ] = A[ p + i - 1 ];
		L_num[ i ] = Num[ p + i - 1 ];
	}
	for ( i = 1; i <= R_len; i ++ ) {
		R[ i ] = A[ q + i ];
		R_num[ i ] = Num[ q + i ];
	}
	L[ L_len + 1 ] = 100000000;
	R[ R_len + 1 ] = 100000000;
	i = j = 1;
	for ( k = p; k <= r; k ++ ) {
		if ( L[ i ] <= R[ j ] ) {
			A[ k ] = L[ i ];
			Num[ k ] = L_num[ i ];
			i ++;
		} else {
			A[ k ] = R[ j ];
			Num[ k ] = R_num[ j ];
			j ++;
		}
	}
}
void Arrange ::Merge_sort( long p, long r ) 
{
	long q ;
	if ( p < r ) {
		q = ( p + r ) / 2;
		Merge_sort( p , q );
		Merge_sort( q + 1, r );
		Merge( p, q , r );
	}
}
long main( void )
{
	Arrange Directory;
	long D_len;

	long List[ MAX ];
	long Count[ MAX ];
	long List_num;											
	long Input_len;											
	
	char Buffer[ 20 ];
	long Buffer_len;

	long sum;
	long by;
	
	bool insert;
	bool duplicate;
	
	long i;
	long l;

	scanf( "%ld", &Input_len );
	for ( l = 0; l < Input_len; l ++ ) {
		Count[ l ] = 0;
	}
	List_num = 0;
	
	// input all the data into List[ ..] & Count[ .. ]
	for ( l = 0; l < Input_len; l ++ ) {
		scanf( "%s", Buffer );
		Buffer_len = strlen( Buffer );
		sum = 0;
		by = 1000000;
		for ( i = 0; i < Buffer_len; i ++ ) {
			if ( Buffer[ i ] >= '0' && Buffer[ i ] <= '9' ) {
				sum += ( Buffer[ i ] - '0' ) * by;
				by /= 10;
			} else if ( Buffer[ i ] >= 'A' && Buffer[ i ] <= 'Z' ) {
				sum += map[ Buffer[ i ] - 'A' ] * by;
				by /= 10;
			} else {
				continue;
			}
		}
		insert = 1;
		for( i = 0; i < List_num; i ++ ) {
			if ( sum == List[ i ] ) {
				Count[ i ] ++;
				insert = 0;
			}
		}
		if ( insert ) {
			List[ List_num ] = sum;
			Count[ List_num ] ++;
			List_num ++;
		}
	}

	// put data into Directory
	duplicate = 0;
	for ( i = 0, D_len = 0; i <  List_num; i ++ ) {
		if ( Count[ i ] > 1 ) {
			duplicate = 1;
			D_len ++;
			Directory.Set_value( List[ i ], Count[ i ], D_len );
		}
	}
	Directory.Set_len( D_len );
	if ( duplicate ) { 
		Directory.Merge_sort( 1, D_len );
		Directory.Output( );
	} else {
		printf( "No duplicates.\n" );
	}

	return 0;
}

• Re:无奈了，用归并做得为什么总是超时呢？ 改掉COUT CIN 还不行啊。。。 (3667) zk54188 2007-11-06 17:04:20