2.cpp

7道ACM题

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


/*
 *     这道题主要是要处理好时空问题.因为测试数据会出现大数,在这种情况下不能用最直接的一下子开辟所有的内存来执行数组的操作.
 * 主要要优化的有两方面:
 *     一个是空间方面.有的测试数据使得图像纵向非常长,其实我们所需要的就只有一个三行的二维数组来进行操作.因为
 * 要比较的一个数它的四周.所以当纵向非常长时我们可以只申请 3 * n 的数组,先填充数据,在第二行进行比较操作.之后把数据前移,再把
 * 新的数组填充到第三行.当然还会有一种情况那就是横向非常长,不过经过尝试这种情况只会发生在只有一行数据的情况,所以在这种情况
 * 我们只要申请一个 3 * 1 的数据,跟上面的情况一样,先填充,再比较,再移位,再填充.
 *     第二个是时间方面.有可能会出现一种情况,就是一个数的数量非常多,这样会使得其中的一些数的四周的数都跟它一样,这样就不用比
 * 了,值就是 0
 */

int main()
{
	// 题目的输入数据是用 RLE 格式,所以要作处理,主要是用两个游标,一个指的是当前的数字,一个是这个数字的数量,当数量变成 0 时
	// 第一个游标将移到下一个数字.当然,因为输出也要求用 RLE 格式,所以也得进行处理
	int n;
	int shuzu[ 1000 ][ 2 ];
	int *save;
	scanf( "%d", &n );

	while ( n != 0 )
	{
		printf( "%d\n", n );
		int a, b;
		int ii = 0;
		int shuzuSize;
		long hang = 0;
		scanf( "%d%d", &a, &b );
		while ( a != 0 || b != 0 )		// 把 RLE 格式的数据装到 shuzu 中
		{
			shuzu[ ii ][ 0 ] = a;
			shuzu[ ii ][ 1 ] = b;
			hang += b;
			ii++;
			scanf( "%d%d", &a, &b );
		}
		shuzuSize = ii;
		
		// 当只需要一行数组时
		if ( hang == n )		
		{
			int save2[ 3 ];
			int fix1 = 0;
			for ( int i = 1; i < 3; i++ )			// 先填充前两个数据
			{
				save2[ i ] = shuzu[ fix1 ][ 0 ];
				shuzu[ fix1 ][ 1 ]--;
				if ( shuzu[ fix1 ][ 1 ] <= 0 )
					fix1++;
				if ( fix1 == shuzuSize )
					break;
			}

			save2[ 0 ] = save2[ 1 ];		// 把第二个数据赋给第一个,便于第一次的比较

			int left, right;
			int ciShu = 1;
			int num, geShu;			// num 表示要输出的数字, geShu 表示要输出数字的个数
			for ( ; ; )				// 开始进行比较,移位等操作
			{
				left = abs( save2[ 1 ] - save2[ 0 ] );
				right = abs( save2[ 2 ] - save2[ 1 ] );

				int temp = 0;
				if ( left > right )
					temp = left;
				else
					temp = right;

				if ( ciShu == 1 )		// 第一次的话先把 geShu 赋 0,下面好操作
				{
					num = temp, geShu = 0;
					ciShu = 0;
				}
				if ( temp == num )		// 如果跟上一个一样的话就把个数加一,如果不一样就输出,并重新给两个变量赋值
					geShu++;
				else
				{
					printf( "%d %d\n", num, geShu );
					num = temp;
					geShu = 1;
				}

				if ( save2[ 1 ] == save2[ 2 ] )		// 如果当后两个数据一样时,说明后面将有可能有大量相同的数据,可以优化
				{
					if ( fix1 < shuzuSize && shuzu[ fix1 ][ 0 ] == save2[ 2 ] )
					{
						int temp = shuzu[ fix1 ][ 1 ] / 2;
						if ( temp >= 1 )
						{
							if ( num != 0 )
							{
								printf( "%d %d\n", num, geShu );
								num = 0, geShu = 2 * temp;
							}
							else
								geShu = 2 * temp + geShu;
							shuzu[ fix1 ][ 1 ] -= 2 * temp;
							if ( shuzu[ fix1 ][ 1 ] == 0 )
								fix1++;
						}
					}
				}

				// 移位
				save2[ 0 ] = save2[ 1 ], save2[ 1 ] = save2[ 2 ];

				// 如果数据没完继续填充
				if ( fix1 < shuzuSize && shuzu[ fix1 ][ 1 ] != 0 )
				{
					save2[ 2 ] = shuzu[ fix1 ][ 0 ];
					shuzu[ fix1 ][ 1 ]--;
					if ( shuzu[ fix1 ][ 1 ] <= 0 )
						fix1++;
				}
				else
					break;
			}
	
			// 最后还要比较最后两个数据
			left = abs( save2[ 1 ] - save2[ 0 ] );
			int temp = left;
			
			if ( temp == num )
				geShu++;
			else
			{
				printf( "%d %d\n", num, geShu );
				num = temp;
				geShu = 1;
			}
			
			printf( "%d %d\n", num, geShu );
			printf( "0 0\n" );
		}

		// 如果不是一行的情况,方法都跟第一种情况差不多
		else
		{
		save = ( int* )malloc( n * 3 * sizeof( int ) );		// 申请三个横向为图宽的数组

		// 第一次填充
		int fix1 = 0;
		for ( int i = n; i < n * 3; i++ )		
		{
			save[ i ] = shuzu[ fix1 ][ 0 ];
			shuzu[ fix1 ][ 1 ]--;
			if ( shuzu[ fix1 ][ 1 ] <= 0 )
					fix1++;
			if ( fix1 == shuzuSize )
				break;
		}

		for ( int i = 0; i < n; i++ )
			save[ i ] = save[ i + n ];

		int max[ 8 ];
		int ciShu = 1;
		int num, geShu;
		for ( ; ; )
		{
			int flag = 1;
			for ( int i = n; i < n * 2; i++ )		// 进行比较
			{
				if ( i == n )
				{
					max[ 0 ] = 0;
					max[ 3 ] = 0;
					max[ 5 ] = 0;
				}
				else
				{
					max[ 0 ] = abs( save[ i ] - save[ i - n - 1 ] );
					max[ 3 ] = abs( save[ i ] - save[ i - 1 ] );
					max[ 5 ] = abs( save[ i ] - save[ i + n - 1 ] );
				}
				if ( i == n * 2 - 1 )
				{
					max[ 2 ] = 0;
					max[ 4 ] = 0;
					max[ 7 ] = 0;
				}
				else
				{
					max[ 2 ] = abs( save[ i ] - save[ i - n + 1 ] );
					max[ 4 ] = abs( save[ i ] - save[ i + 1 ] );
					max[ 7 ] = abs( save[ i ] - save[ i + n + 1 ] );
				}
				
				max[ 1 ] = abs( save[ i ] - save[ i - n ] );
				max[ 6 ] = abs( save[ i ] - save[ i + n ] );

				// 取 8 个数中最大的
				int temp = 0;
				for ( int i = 0; i < 8; i++ )
					if ( max[ i ] > temp )
						temp = max[ i ];

				// 输出
				if ( ciShu == 1 )
				{
					num = temp, geShu = 0;
					ciShu = 0;
				}
				if ( temp == num )
					geShu++;
				else
				{
					printf( "%d %d\n", num, geShu );
					num = temp;
					geShu = 1;
				}
			}

			// 如果第二行的数据跟第三行的数据完全一样,则有可能后面有大量相同的数据,可以优化
			for ( int i = n; i < n * 3 - 1; i++ )
				if ( save[ i + 1 ] != save[ i ] )
				{
					flag = 0;
					break;
				}
			if ( flag == 1 )		// 如果第二行的数据跟第三行的数据完全一样
			{
				if ( fix1 < shuzuSize && shuzu[ fix1 ][ 0 ] == save[ n ] )	// 判断下一个要填充的数字跟目前的数字是否一样
				{
				int temp = shuzu[ fix1 ][ 1 ] / n;		
				if ( temp >= 1 )				// 如果目前数字的数量大于二行时,则可以用取余操作,直接把中间的结果都计为 0
				{
					if ( num != 0 )
					{
						printf( "%d %d\n", num, geShu );
						num = 0, geShu = n * temp;
					}
					else
						geShu = n * temp + geShu;
					shuzu[ fix1 ][ 1 ] -= n * temp;
					if ( shuzu[ fix1 ][ 1 ] == 0 )
						fix1++;
				}
				}
			}

			// 移位
			for ( int i = 0; i < n * 2; i++ )
				save[ i ] = save[ i + n ];
			
			// 数据没完就再填充
			int flag1 = 0;
			if ( fix1 < shuzuSize && shuzu[ fix1 ][ 1 ] != 0 )
			{
				for ( int i = n * 2; i < n * 3; i++ )
				{
					save[ i ] = shuzu[ fix1 ][ 0 ];
					shuzu[ fix1 ][ 1 ]--;
					if ( shuzu[ fix1 ][ 1 ] <= 0 )
						fix1++;
				}
				flag1 = 1;
			}

			if ( flag1 == 0 )
				break;
		}

		// 比较最后一行数据
		for ( int i = n; i < n * 2; i++ )
		{
			if ( i == n )
			{
				max[ 0 ] = 0;
				max[ 3 ] = 0;
			}
			else
			{
				max[ 0 ] = abs( save[ i ] - save[ i - n - 1 ] );
				max[ 3 ] = abs( save[ i ] - save[ i - 1 ] );
			}
			if ( i == n * 2 - 1 )
			{
				max[ 2 ] = 0;
				max[ 4 ] = 0;
			}
			else
			{
				max[ 2 ] = abs( save[ i ] - save[ i - n + 1 ] );
				max[ 4 ] = abs( save[ i ] - save[ i + 1 ] );
			}
				
			max[ 1 ] = abs( save[ i ] - save[ i - n ] );
			max[ 5 ] = 0;
			max[ 6 ] = 0;
			max[ 7 ] = 0;

			int temp = 0;
			for ( int i = 0; i < 8; i++ )
				if ( max[ i ] > temp )
					temp = max[ i ];
			if ( temp == num )
				geShu++;
			else
			{
				printf( "%d %d\n", num, geShu );
				num = temp;
				geShu = 1;
			}
		}

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

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

	printf( "0\n" );
	return 0;
}