4.cpp

7道ACM题

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


/*
 * 这道题最主要的就是对快速排序进行优化,前面的就是数字和字符的转换而已
 */

int main()
{
	void Quick_Sort( int *v, int vSize );

	int ziMu[ 26 ];
	ziMu[ 0 ] = 2, ziMu[ 1 ] = 2, ziMu[ 2 ] = 2, ziMu[ 3 ] = 3, ziMu[ 4 ] = 3, ziMu[ 5 ] = 3;
	ziMu[ 6 ] = 4, ziMu[ 7 ] = 4, ziMu[ 8 ] = 4, ziMu[ 9 ] = 5, ziMu[ 10 ] = 5, ziMu[ 11 ] = 5;
	ziMu[ 12 ] = 6, ziMu[ 13 ] = 6, ziMu[ 14 ] = 6, ziMu[ 15 ] = 7, ziMu[ 16 ] = 0, ziMu[ 17 ] = 7;
	ziMu[ 18 ] = 7, ziMu[ 19 ] = 8, ziMu[ 20 ] = 8, ziMu[ 21 ] = 8, ziMu[ 22 ] = 9; ziMu[ 23 ] = 9;
	ziMu[ 24 ] = 9, ziMu[ 25 ] = 0;

	int n;
	scanf( "%d", &n );

	int *shuzu = ( int* )malloc( n * sizeof( int ) );

	char ch[ 50 ];
	for ( int i = 0; i < n; i++ )
	{
		scanf( "%s", ch );
		int size = strlen( ch );
		int sum = 0, temp = 1, num;
		for ( int j = size - 1; j >= 0; j-- )
		{
			if ( ch[ j ] >= 48 && ch[ j ] <= 57 )
			{
				num = ch[ j ] - 48;
				sum += num * temp;
				temp *= 10;
			}
			else if ( ch[ j ] >= 65 && ch[ j ] <= 90 )
			{
				num = ziMu[ ch[ j ] - 65 ];
				sum += num * temp;
				temp *= 10;
			}
		}

		shuzu[ i ] = sum;
		
	}

	Quick_Sort( shuzu, n );

	int flag = 0;
	int temp = shuzu[ 0 ];
	int num = 1;
	for ( int i = 1; i < n; i++ )
	{
		if ( shuzu[ i ] == temp )
			num++;
		else 
		{
			if ( num > 1 )
			{
				flag = 1;
				int a = temp / 10000;
				int b = temp - temp / 10000 * 10000;
				if ( a >= 100 )
					printf( "%d-", a );
				if ( a < 100 && a >= 10 )
					printf( "0%d-", a );
				if ( a < 10 )
					printf( "00%d-", a );
				if ( b >= 1000 )
					printf( "%d ", b );
				if ( b < 1000 && b >= 100 )
					printf( "0%d ", b );
				if ( b < 100 && b >= 10 )
					printf( "00%d ", b );
				if ( b < 10 )
					printf( "000%d ", b );

				printf( "%d\n", num );
			}
			
			temp = shuzu[ i ];
			num = 1;
		}
	}
	if ( num > 1 )
			{
				flag = 1;
				int a = temp / 10000;
				int b = temp - temp / 10000 * 10000;
				if ( a >= 100 )
					printf( "%d-", a );
				if ( a < 100 && a >= 10 )
					printf( "0%d-", a );
				if ( a < 10 )
					printf( "00%d-", a );
				if ( b >= 1000 )
					printf( "%d ", b );
				if ( b < 1000 && b >= 100 )
					printf( "0%d ", b );
				if ( b < 100 && b >= 10 )
					printf( "00%d ", b );
				if ( b < 10 )
					printf( "000%d ", b );

				printf( "%d\n", num );
			}

	if ( flag == 0 )
		printf( "No duplicates.\n" );
}


// 快速排序,从两方面进行优化,一个是在选关键字的时候从当前选第一个,中间和最后一个,并选这三个当中的中间那一个,为的是能把数组
// 分成较相等的两部分;其次是在跟关键字比较大小的时候顺便执行类似于冒泡排序的操作,当相邻两个数的顺序不符合时交换两个数,当发
// 现当前这一部分没有发生交换操作时,即说明这部分是有序,以后也就不用再处理这一块了
void Quick_Sort( int *v, int vSize )
{
	void QSort( int *v, int low, int high, int *low1, int *high1, int vSize );

	int low1, high1;
	low1 = 1, high1 = 1;
	QSort( v, 0, vSize - 1, &low1, &high1, vSize );
}
		
void QSort( int *v, int low, int high, int *low1, int *high1, int vSize )
{
	int pivotloc;
	int Partition( int *v, int low, int high, int *low1, int *high1, int vSize );

	if ( low < high )
	{
		int low2, high2;
		pivotloc = Partition( v, low, high, low1, high1, vSize );
		low2 = *low1, high2 = *high1;
		if ( low2 == 1 )			// 如果前部分已经有序,就不用再对其进行处理
			QSort( v, low, pivotloc - 1, low1, high1, vSize );

		if ( high2 == 1 )			// 如果后部分已经有序,就不用再对其进行处理
			QSort( v, pivotloc + 1, high, low1, high1, vSize );
	}
}

// 最关键的优化部分
int Partition( int *v, int low, int high, int *low1, int *high1, int vSize )
{
	// 选取关键字
	int temp;
	int m = ( low + high ) / 2;
	if ( v[ low ] >= v[ high ] && v[ low ] <= v[ m ] )
		temp = low;
	else if ( v[ high ] >= v[ low ] && v[ high ] <= v[ m ] )
		temp = high;
	else
		temp = m;
	m = v[ temp ];
	v[ temp ] = v[ low ];
	v[ low ] = m;

	int pivotloc = v[ low ];
	
	*low1 = 0, *high1 = 0;
	while ( low < high )
	{
		while ( low < high && v[ high ] >= pivotloc )
		{
			high--;
			if ( vSize - 1 - high > 1 && v[ high + 1 ] > v[ high + 2 ] )		// 当次序不符合时交换
			{
				temp = v[ high + 1 ];
				v[ high + 1 ] = v[ high + 2 ];
				v[ high + 2 ] = temp;
				*high1 = 1;				// 如果发生交换就把标示 low1 变 1, 如果都没发生交换这个值就不会变
			}
		}
		v[ low ] = v[ high ];

		while ( low < high && v[ low ] <= pivotloc )
		{
			low++;
			if ( low > 1 && v[ low - 1 ] < v[ low - 2 ] )
			{
				temp = v[ low - 1 ];
				v[ low - 1 ] = v[ low - 2 ];
				v[ low - 2 ] = temp;
				*low1 = 1;
			}
		}
		v[ high ] = v[ low ];
	}
	v[ low ] = pivotloc;

	return low;
}