P4842 舞会（基础）

解题思路

**第一步，把男生女生分别排成两队。**男生从1号到x号依次排好，女生从1号到y号依次排好。可以用两个数组当作队列，队头（hm、hf）指向下一首舞曲要出场的男生和女生，队尾（tm、tf）用来放回到队伍末尾的人。

**第二步，每首舞曲怎么配对？**伴奏响起时，男生队头的人和女生队头的人各出列，组成一对舞伴，把他们打印出来。跳完这首舞曲后，两个人不会离开，而是回到自己队伍的末尾继续排队，等待下一首舞曲再次轮到自己。这就像我们玩“循环排队”一样。

**第三步，循环往复，直到放完n首舞曲。**因为人数不一样也没关系，每个人都是在自己那队里按顺序循环出场。比如男生只有3人，女生有5人，那么男生会一直按 1、2、3、1、2、3……循环，女生按 1、2、3、4、5……循环。

**第四步，注意数组要开大一点。**因为每跳完一首舞，出队的人都要排回队尾，队尾的下标会一直往后涨，最多涨到 n+人数 那么多。题目说n最大接近1000，所以把数组开到2005就万无一失，不会越界。

**举例子验证。**输入 3 5 9：第一首舞曲男生1号、女生1号；第二首2号和2号；第三首3号和3号；第四首男生轮回1号，女生是4号……依次推下去，最后一首是男生3号、女生4号，和样例输出完全一致。

参考代码

// P4842 舞会：男队女队各一个队列，每首舞曲队首配对并回队尾
#include <iostream>
#include <cstdio>
using namespace std;
int x, y, n;
int qm[2005], qf[2005];  // 队尾最多到 n+人数 < 2000
int hm, tm, hf, tf;
int main() {
    scanf("%d%d%d", &x, &y, &n);
    for (int i = 1; i <= x; i++) qm[tm++] = i;  // 男队入队
    for (int i = 1; i <= y; i++) qf[tf++] = i;  // 女队入队
    for (int i = 0; i < n; i++) {
        int b = qm[hm++];  // 男队队首出队
        int g = qf[hf++];  // 女队队首出队
        printf("%d %d\n", b, g);
        qm[tm++] = b;      // 回到队尾等待下一轮
        qf[tf++] = g;
    }
    return 0;
}

复杂度分析

每个男生、女生只入队一次，之后每首舞曲出队配对再回队尾，都是常数时间操作，一共要放n首舞曲，所以总时间是O(n)。空间上需要存下男生队和女生队，约O(x+y)。x、y、n都不超过1000，这个算法非常快。