一种排序（南阳理工oj 题目8）

题目链接  http://acm.nyist.net/JudgeOnline/problem.php?pid=8

一种排序

时间限制： 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 解题思路：

这道题，用到了STL里面的sort排序。需要注意的是长方形的 长 和 宽 提前没有确定，要自己提前确定（大的数是长，小的数是宽）。

代码：

#include<iostream> #include<cstring> #include<algorithm> //sort排序所需要的头文件 using namespace std; struct qq //用结构体保存每一个长方形的编号、长、宽 { int x; int l; int w; }a[10005]; bool com(qq a,qq b) //这个额sort排序便实现了先按照编号排序，再按照长，再按照宽排序 { if(a.x<b.x) //如果前一个的编号<后一个的编号，返回真 return true; else if(a.x==b.x&&a.l<b.l) //如果编号相等&&前一个的长>后一个的长，返回真 return true; else if(a.x==b.x&&a.l==b.l&&a.w<b.w) //如果编号、长相等&&前一个的宽>后一个的宽，返回真 return true; else return false; //其它情况返回假 } int main() { int n,m; cin>>n; while(n--) { memset(a,0,sizeof(a)); //让a数组每一个元素都等于0,方便下面的去重 cin>>m; for(int i=0;i<=m-1;i++) { cin>>a[i].x>>a[i].l>>a[i].w; if(a[i].w>a[i].l) //题目说大的数是长，小的数是宽，所以要提前选择好长和宽 { int t=a[i].w; a[i].w=a[i].l; a[i].l=t; } } sort(a,a+m,com); for(int i=0;i<=m-1;i++) { if(a[i+1].x!=a[i].x||a[i+1].l!=a[i].l||a[i+1].w!=a[i].w) //去重操作 cout<<a[i].x<<' '<<a[i].l<<' '<<a[i].w<<endl; } } return 0; }