#742. 周末舞会

· · 个人记录

742. 周末舞会

Background

Special for beginners, ^_^

Description

假设在周末舞会上，男士们和女士们进入舞厅时，各自排成一队。跳舞开始时，依次从男队和女队的队头上各出一人配成舞伴。规定每个舞曲只能有一对跳舞者。若两队初始人数不相同，则较长的那一队中未配对者等待下一轮舞曲。现要求写一个程序，模拟上述舞伴配对问题。

Format

Input

第一行男士人数 m 和女士人数 n (m≤1000,n≤1000)

第二行舞曲的数目 k (k≤1000)。

Output

共 k 行，每行两个数，表示配对舞伴的序号，男士在前，女士在后。

Samples

输入数据 1

2 4
6

输出数据 1

1 1
2 2
1 3
2 4
1 1
2 2

Limitation

1s, 1024KiB for each test case.

对于这一题，我用队列解决。

首先设两个队列qa和qb，设两个对头和两个队尾。

接下来男生和女生从对尾插入，并循环遍历舞曲数目。对头的两人跳舞，然后到队尾去，队首改变，队尾改变即可。

代码实现：

//#742. 周末舞会
#include <bits/stdc++.h>
using namespace std;
const int N=2007; //根据k定义队列长度 
int qa[N], qb[N], fa, ra, fb, rb, m, n, k; 
int main(){
    scanf("%d%d%d", &m, &n, &k);
    for (int i=1;i<=m;++i)
        qa[ra++]=i; //男生从队尾插入  
    for (int i=1;i<=n;++i)
        qb[rb++]=i; //女生从队尾插入 
    while (k--) {
        printf("%d %d\n", qa[fa], qb[fb]); //从队首找一人跳舞 
        qa[ra++]=qa[fa++]; //队首到队尾排队, 队首改变，队尾改变 
        qb[rb++]=qb[fb++];
    }
    return 0;
}

注意事项：

对头和队尾千万不能搞混哦！