开开心心学算法--一种排序

时间限制：3000ms | 内存限制：65535KB

难度：3

描述

现在有很多长方形，每一个长方形都有一个编号，这个编号可以重复；还知道这个长方形的宽和长，编号、长、宽都是整数；现在要求按照一下方式排序（默认排序规则都是从小到大）；

1.按照编号从小到大排序

2.对于编号相等的长方形，按照长方形的长排序；

3.如果编号和长都相同，按照长方形的宽排序；

4.如果编号、长、宽都相同，就只保留一个长方形用于排序,删除多余的长方形；最后排好序按照指定格式显示所有的长方形；

输入

第一行有一个整数 0<n<10000,表示接下来有n组测试数据；
每一组第一行有一个整数 0<m<1000，表示有m个长方形；
接下来的m行，每一行有三个数 ，第一个数表示长方形的编号，

第二个和第三个数值大的表示长，数值小的表示宽，相等
说明这是一个正方形（数据约定长宽与编号都小于10000）；

输出

顺序输出每组数据的所有符合条件的长方形的 编号 长 宽

样例输入

1
8
1 1 1
1 1 1
1 1 2
1 2 1
1 2 2
2 1 1
2 1 2
2 2 1

样例输出

1 1 1
1 2 1
1 2 2
2 1 1
2 2 1

这道题虽然题目长，但是很好理解，可是写代码的时候又觉得哪里不对了，总觉得自己写的太复杂，可是又感觉必须要有这些过程。真可谓是一波三折啊。哈哈哈

废话不多说了，下面是我的程序：

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

//用结构体保存数据
typedef struct rectangle { 
	int sequence; 
	int chang;
	int wide;
	int flag;  //标记重复的
}RECT;

//排序，这里用交换指针的地址来排序
void paixu( RECT *p,RECT *q)
{
	RECT *t;
	t=(RECT *)malloc(sizeof(RECT));
	*t=*p;
	*p=*q;
	*q=*t;
	free(t);
}

int main()
{
	int n,m,i,j,x,y;//中间或临时变量
	RECT *Rect[1000];	
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d",&m);
		for(i=0;i<m;i++)
		{
			Rect[i] = (RECT *)malloc(sizeof(RECT));//动态分配内存用于保存输入的值
			scanf("%d %d %d",&Rect[i]->sequence,&x,&y);
			if( x > y )   //将大的作为长方形的长
			{
				Rect[i]->chang = x;
				Rect[i]->wide = y;
			}
			else
			{
				Rect[i]->chang = y;
				Rect[i]->wide = x;
			}
			
		}
		for(i=0;i<m;i++)
			Rect[i]->flag = 1;   //标志初始化，默认为没有需要丢弃的
		for(i=0;i<m-1;i++)   //循环比较
			for(j=i+1;j<m;j++)
			{	//前面的序号大，并且没有废弃的数据
				if(Rect[i]->sequence > Rect[j]->sequence && Rect[i]->flag && Rect[j]->flag)
				{
					paixu(Rect[i],Rect[j]);
					continue;
				}
				else if( !Rect[i]->flag ) //如果前面一个数是废弃的数，直接进行下一轮比较
					break;
				else if( ! Rect[j]->flag) //如果后一个数是废弃的数，则跳过去，继续和下一个比较
					continue;
				else if(Rect[i]->sequence == Rect[j]->sequence)  //序号相等时比较长
				{
					if(Rect[i]->chang > Rect[j]->chang)
					{
						paixu(Rect[i],Rect[j]);
						continue;
					}
					else if(Rect[i]->chang == Rect[j]->chang)  //长相等时比较宽
					{
						if(Rect[i]->wide > Rect[j]->wide)
						{
							paixu(Rect[i],Rect[j]);
							continue;
						}
						else if(Rect[i]->wide == Rect[j]->wide )  //宽相等时将其中一个数据废弃
							Rect[i]->flag = 0;
					}	
				
				}	
			}//end for(j=i+1;...)			
		for(i=0;i<m;i++)  //输出
		{
			if( !(Rect[i]->flag) )
				continue;
			printf("%d %d %d \n",Rect[i]->sequence,Rect[i]->chang,Rect[i]->wide);
		}
	
		for(i=0;i<m;i++)  //释放内存
			free(Rect[i]);
	}//end while(n--)
	return 1;
}

运行时间12，内存308。

收获：人脑思维和电脑的思维方式是很不一样的，很多人脑觉得很容易的事件，电脑处理起来就很复杂（比如用眼睛去判断一个人是谁和用电脑去判断），但也有很多人脑觉得很复杂的事情，电脑处理起来就觉得很轻松（比如大整数的运算）。所以我们需要合理的利用电脑的思维方式去解决我们生活中的难题。作为一个程序员更是要深入了解和运用电脑思维，创造一个一个的奇迹。