一种排序

浏览数：14 / 时间：2015年06月08日

一种排序

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

难度：3

描述

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

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

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

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

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

输入

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

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

输出

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

样例输入

样例输出

来源

经典题目

上传者

iphxer

思路：这题是先排序，再删减。。昨天我是先删减，再排序，结果wa了。。在讨论组里看到有个大神写的是先sort，再删减。。我心里想不一样吗。。额，肯定是不一样的。

比如把长方形的3个属性用小写字母表示。比如开始输入是abca.先排序aabc,然后删减abc，得到正解。但是如果先删减，b数组里面存放仍然是abca,再排序aabc，就会有重复的。。需要注意。

#include<iostream>
#include<algorithm>
using namespace std;
struct cfx
{
	int length;
	int width;
	int num;
};
int cmp(cfx a,cfx b)
{
	if(a.num!=b.num)
		return a.num<b.num;//升序
	 else if(a.num==b.num &&a.length!=b.length)
		return a.length<b.length;
	else if(a.num==b.num &&a.length==b.length)
		return a.width<b.width;
}
int main()
{
	int n,m,i,k;
	cfx a[1000];
	cfx b[1000];
	cin>>n;
	while(n--)
	{
		k=0;
      cin>>m;//m个长方形
	  for(i=0;i<m;i++)
	  {
		  cin>>a[i].num>>a[i].length>>a[i].width;
		  if(a[i].length<a[i].width)
		  {
			  int t;
			  t=a[i].length;
			  a[i].length=a[i].width;
			  a[i].width=t;	  
		  }
	  }
	   sort(a,a+m,cmp);
		  for(i=0;i<m;i++) //aabbcc
		  {
             while(i<m-1 &&a[i].length==a[i+1].length &&a[i].num==a[i+1].num &&a[i].width==a[i+1].width)
			 {
				 i++;
			 }
			 b[k++]=a[i];	 
		  }
         
		  for(i=0;i<k;i++)
		  {
			  cout<<b[i].num<<" "<<b[i].length<<" "<<b[i].width<<endl;
		  }
      
	}
	return 0;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

一种排序