L1-049 天梯赛座位分配

题目:

天梯赛每年有大量参赛队员，要保证同一所学校的所有队员都不能相邻，分配座位就成为一件比较麻烦的事情。为此我们制定如下策略：假设某赛场有 N 所学校参赛，第 i 所学校有 M[i] 支队伍，每队 10 位参赛选手。令每校选手排成一列纵队，第 i+1 队的选手排在第 i 队选手之后。从第 1 所学校开始，各校的第 1 位队员顺次入座，然后是各校的第 2 位队员…… 以此类推。如果最后只剩下 1 所学校的队伍还没有分配座位，则需要安排他们的队员隔位就坐。本题就要求你编写程序，自动为各校生成队员的座位号，从 1 开始编号。

输入格式:

输入在一行中给出参赛的高校数 N （不超过100的正整数）；第二行给出 N 个不超过10的正整数，其中第 i 个数对应第 i 所高校的参赛队伍数，数字间以空格分隔。

输出格式:

从第 1 所高校的第 1 支队伍开始，顺次输出队员的座位号。每队占一行，座位号间以 1 个空格分隔，行首尾不得有多余空格。另外，每所高校的第一行按“#X”输出该校的编号X，从 1 开始。

输入样例:

3

3 4 2

输出样例:

#1
1 4 7 10 13 16 19 22 25 28
31 34 37 40 43 46 49 52 55 58
61 63 65 67 69 71 73 75 77 79
#2
2 5 8 11 14 17 20 23 26 29
32 35 38 41 44 47 50 53 56 59
62 64 66 68 70 72 74 76 78 80
82 84 86 88 90 92 94 96 98 100
#3
3 6 9 12 15 18 21 24 27 30
33 36 39 42 45 48 51 54 57 60

解决方案:

无注释版:

#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1009;
int ans[N][N];

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n;
    cin >> n;

    int col = -1;
    for (int i = 1, num; i <= n; ++i) {
        cin >> num;
        ans[i][0] = num * 10;
        col = max(col, num * 10);
    }

    int num = 0, pre = 0;

    for (int i = 1; i <= col; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i > ans[j][0]) continue;
            if (pre == j) ++num;
            ans[j][i] = ++num;
            pre = j;
        }
    }

    for (int i = 1; i <= n; ++i) {
        cout << '#' << i;
        for (int j = 1; j <= ans[i][0]; ++j) {
            if (j % 10 == 1) cout << '\n' << ans[i][j];
            else cout << ' ' << ans[i][j];
        }
        cout << '\n';
    }

    return 0;
}

有注释版:

#include <algorithm> // 引入算法库，用于使用 max 函数
#include <iostream>  // 引入输入输出流库，以便进行输入输出操作

using namespace std;

const int N = 1009; // 定义常量 N，表示最多可以处理的学校数量
int ans[N][N]; // 二维数组，用来存储每个队伍的座位号

int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); // 优化输入输出，提高效率

    int n;
    cin >> n; // 读取学校数量

    int col = -1; // 初始化最大列数，用于记录队伍总数
    for (int i = 1, num; i <= n; ++i) {
        cin >> num; // 读取第 i 所学校的队伍数量
        ans[i][0] = num * 10; // 将每所学校的参赛选手总数（每队 10 人）存入 ans 的第一列
        col = max(col, num * 10); // 更新最大的列数（即最大队伍的总人数）
    }

    int num = 0, pre = 0; // 初始化座位编号 num 和上一个队伍索引 pre

    // 遍历每个可能的座位编号
    for (int i = 1; i <= col; ++i) { // i 表示当前座位位置
        for (int j = 1; j <= n; ++j) { // j 表示当前正在处理的学校
            if (i > ans[j][0]) continue; // 检查如果当前 seat i 超过该学校的队伍总数，则跳过该学校
            if (pre == j) ++num; // 如果前一个队伍是同一所学校，则座位编号加一，确保不相邻
            ans[j][i] = ++num; // 将座位编号分配给当前学校的选手
            pre = j; // 更新上一个队伍信息为当前学校
        }
    }

    // 输出每所学校的座位分配结果
    for (int i = 1; i <= n; ++i) { // 遍历每所学校
        cout << '#' << i; // 打印学校编号
        for (int j = 1; j <= ans[i][0]; ++j) { // 遍历每个学校的座位编号
            if (j % 10 == 1) cout << '\n' << ans[i][j]; // 每10个座位换行输出
            else cout << ' ' << ans[i][j]; // 输出座位编号，并在之间加一个空格
        }
        cout << '\n'; // 输出学校编号后换行
    }

    return 0; // 程序正常结束
}

解题思路:

先计算并存入每个学校的总人数。

int col = -1; // 初始化最大列数，用于记录队伍总数
for (int i = 1, num; i <= n; ++i) {
    cin >> num; // 读取第 i 所学校的队伍数量
    ans[i][0] = num * 10; // 将每所学校的参赛选手总数（每队 10 人）存入 ans 的第一列
    col = max(col, num * 10); // 更新最大的列数（即最大队伍的总人数）
}

然后遍历每一个座位编号。

for (int i = 1; i <= col; ++i) { // i 表示当前座位位置
    for (int j = 1; j <= n; ++j) { // j 表示当前正在处理的学校
        if (i > ans[j][0]) continue; // 检查如果当前 seat i 超过该学校的队伍总数，则跳过该学校
        if (pre == j) ++num; // 如果前一个队伍是同一所学校，则座位编号加一，确保不相邻
        ans[j][i] = ++num; // 将座位编号分配给当前学校的选手
        pre = j; // 更新上一个队伍信息为当前学校
    }
}

第一个if 的意思是，如果座位位置号达到该学校的最大总人数,则跳过。

第二个if的意思是，如果只剩一个队伍的人排座位了，那么位置号就要加一隔开。

就拿本题的测试样例来说，如果此时有三个队伍的队员在排座位，那么第一个if 不会触发，当i的值达到与队员人数最少的那个一个学校相等后，之后if 才会触发。如果此时只剩人数最多的那个学校的队员在排座位号了，那么第二个if就会触发条件，确保相同学校的队员隔开。

最后就是按照题目要求的格式，打印出相应的答案了。

 for (int i = 1; i <= n; ++i) { // 遍历每所学校
     cout << '#' << i; // 打印学校编号
     for (int j = 1; j <= ans[i][0]; ++j) { // 遍历每个学校的座位编号
         if (j % 10 == 1) cout << '\n' << ans[i][j]; // 每10个座位换行输出
         else cout << ' ' << ans[i][j]; // 输出座位编号，并在之间加一个空格
     }
     cout << '\n'; // 输出学校编号后换行
 }