标签：模拟
题目描述Description
卡卡西的班主任鸣人老师在教学管理方面有自己的一套独特的方法。就比如，同样是安排座位，他们班级的做法就非常与众不同。具体做法是这样的：班级的n个同学按照序号依次将自己期望的同桌序号写在纸上，统一交由鸣人老师。鸣人老师进行统计，按照得票数从高到低的顺序，先安排得票高的同学的同桌，如果该同桌未被安排，则安排给对应同学，如果已经被安排了，则按照序号从头挑选没有安排同桌的同学。
输入描述Input Description
2行，第一行班级人数n，第二行按照序号依次给出每一个同学期望的同桌的序号。
输出描述Output Description
n行，每行两个数字，中间用空格隔开，第一个数是序号，第二个数是该序号同学同桌的序号。
样例输入Sample Input
8
3 3 4 6 6 8 2 3
样例输出Sample Output
1 2
2 1
3 4
4 3
5 7
6 8
7 5
8 6
数据范围及提示Data Size & Hint
样例解释：
有3个人想跟3号坐，3号第一个选择，选择4号；有2个人想跟6号坐，6号第二个选择，选择8号；有1个人想跟2号坐，2号第三个选择，因为3号已经被选择，所以2号只能选择1号；余下5号和7号正好同桌。
数据范围：
n是偶数，且4<=n<=50。
说明：
如果两人得票数一样，序号小的人先选。
分析：绝世好水的题，娱乐大众23333，教练竟然怀疑是二分图匹配（笑）
实际上是小学组题目
code
#include<bits/stdc++.h>
using namespace std;
struct node{int want,rate,id,ans;}x[56];//want表示期望和某人坐同桌，rate表示受欢迎程度，id表示读入时的序号，ans表示最终答案和谁坐同桌
int n;
bool cmp1(node a,node b){return a.rate==b.rate?a.id<b.id:a.rate>b.rate;}
bool cmp2(node a,node b){return a.id<b.id;}
int main()
{
cin>>n;
for(int i=1;i<=n;i++){
cin>>x[i].want;
x[x[i].want].rate++;
x[i].id=i;
}
sort(x+1,x+1+n,cmp1);//按受欢迎程度排序
for(int i=1;i<=n;i++){
if(x[i].ans>0)continue;//如果这个人已经有同桌了，就跳过
int flag=0;
for(int j=1;j<=n;j++)
if(x[j].id==x[i].want){//寻找期望中的同桌
if(x[j].ans==0){//如果期望中的同桌还未匹配，那么就与其匹配
x[j].ans=x[i].id;
x[i].ans=x[i].want;
break;
}
flag=1;//如果期望中的同桌被其他人匹配过了，那么打上标记
}
if(flag==1)//期望中的同桌被其他人匹配过了，重新找为匹配的同桌
for(int j=i+1;j<=n;j++)//前i-1个人肯定都已匹配完毕，从第i+1个人开始找
if(x[j].ans==0){
x[j].ans=x[i].id;
x[i].ans=x[j].id;
break;
}
}
sort(x+1,x+1+n,cmp2);//按读入的id值重新排序输出
for(int i=1;i<=n;i++)cout<<x[i].id<<' '<<x[i].ans<<endl;
return 0;
}
