一种排序

一种排序

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

难度：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

来源

经典题目

上传者

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;
}

<dd style="color: rgb(70, 70, 70); font-family: Tahoma, Arial, sans-serif, simsun; font-size: 14px; margin: 0px; padding: 0px;"><pre name="code" class="cpp">//今天又看了一下,能够不用申请b数组。。

<span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; background-color: rgb(253, 253, 253);">#include<iostream></span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">#include<algorithm></span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">using namespace std;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">struct cfx</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">{</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">int chang;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">int kuan;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">int num;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">};</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">int cmp(cfx a,cfx b)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">{</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">if(a.num!=b.num)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">return a.num<b.num;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">else if(a.num==b.num &&a.chang!=b.chang)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">return a.chang<b.chang;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">else if(a.num==b.num &&a.chang==b.chang &&a.kuan!=b.kuan)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">return a.kuan<b.kuan;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">}</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">int main()</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">{</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">int T,m,i;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">cfx a[1000];</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">cin>>T;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">while(T--)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">{</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">cin>>m;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">for(i=0;i<m;i++)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">{</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">cin>>a[i].num>>a[i].chang>>a[i].kuan;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">if(a[i].chang<a[i].kuan)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">{</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">int t;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">t=a[i].chang;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">a[i].chang=a[i].kuan;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">a[i].kuan=t;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">}</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">}</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">sort(a,a+m,cmp);//排序</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">for(i=0;i<m;i++)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">{</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">while(i<m-1 && a[i].chang==a[i+1].chang &&a[i].num==a[i+1].num && a[i].kuan==a[i+1].kuan)</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">{</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">i++;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">}</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">cout<<a[i].num<<" "<<a[i].chang<<" "<<a[i].kuan<<endl;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">}</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">}</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">return 0;</span><br style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);" /><span style="font-family: Tahoma, Arial, sans-serif, simsun; font-size: 12.800000190734863px; line-height: 19.5px; text-indent: 20px; background-color: rgb(253, 253, 253);">}</span>

版权声明：本文博客原创文章，博客，未经同意，不得转载。