本文主要是介绍速配游戏,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
Problem Description
有一个速配电视节目。N位男士和N位女士要在摄像机前选出他们合适的伴侣。每位女士按照其对每位男士作为配偶的偏爱程度给每位男士排名次,每位男士也按照对其每位女士作为配偶的偏爱程度给每位女士排名次。这些名次不允许并列。然后每位男士将向心仪的对象求婚,经过“残酷”的竞争之后各自找到适合的伴侣。
最开始的时候每位男士都没有被任何一位女士拒绝。求婚环节会经过很多轮进行,每一轮:
(1)每位男士从还没有拒绝过自己的女士中选出自己认为最理想的一个,并向她求婚。
(2)每位女士从所有这一轮中从向她求婚的男士中选出自己认为最理想的一个,并不答应,也不拒绝。她把其余向她求婚的男士都婉言拒绝掉。
经过若干轮求婚之后,在某一轮,幸运的事情发生了:所有的女士都恰好有一个求婚者,所有的男士都找到一个心仪的对象。主持人将继续指出这个配对方式的神奇之处:没有任意的两个配对,例如男士A和女士a配对,男士B和女士b配对,使得在A心目中b较a更理想,而且在b心目中A较B更理想(这样A和b就会“私奔”)。因此,主持人总结说,这个配对是非常合理的。(他知道,这种情况一定会发生的。)
主持人在节目之前已经知道男士和女士之间的偏爱情况,他想预先知道最后的匹配结果是怎么样的,你能帮帮他吗?
Input
有多组输入数据,每组数据的第一行一个数字N(1<=N<=1000),
以下N*2行,每行N个数字。第i+1行(1<=i<=N)表示编号为i的男士对女士们的排序(从最喜欢的到最不喜欢的)。第N+j+1行(1<=j<=N)表示编号为j的女士对男士们的排序(同样从最喜欢的到最不喜欢的)
Output
对于每组输入,输出N行,每行包括一个数字。第i行的数字表示与编号为i的男士匹配的女士的编号。
Sample Input
3
1 2 3
2 3 1
2 1 3
3 2 1
2 3 1
2 3 1
Sample Output
3
2
1
//标程:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX = 1010;
int a[MAX][MAX], p[MAX], q[MAX];
int b[MAX][MAX], c[MAX][MAX];
int n;int main()
{
// freopen("a.txt","r",stdin);int i, j, s, t, k, x;while(scanf("%d",&n)!=EOF){for(i = 1; i <= n; ++ i)for(j = 1; j <= n; ++ j)scanf("%d",&a[i][j]);for(i = 1; i <= n; ++ i)for(j = 1; j <= n; ++ j){scanf("%d",&k);b[i][j] = k;c[i][k] = j;}for(i = 1; i <= n; ++ i)p[i] = 1;for(x = 0; !x ;){x = 1;memset(q,0,sizeof(q));for(i = 1; i <= n; ++ i){j = a[i][p[i]];if(q[j] == 0) q[j] = i;else{x = 0;s = c[j][i];t = c[j][q[j]];if(s > t) p[i] ++;else p[q[j]] ++, q[j] = i;}}}for(i = 1; i <= n; ++ i)printf("%d\n",a[i][p[i]]);}return 0;
}
这篇关于速配游戏的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!