PTA 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<stdio.h>
int main()
{int n = 0;scanf("%d", &n);int num[101] = { 0 };int i = 0;int max = 0;int id = 0;int pos[101][11][11] = { 0 };int pre = 0;//输入各高校队伍数并求出最大的队伍数for (i = 1; i <= n; i++){scanf("%d", &num[i]);max = num[i] > max ? num[i] : max;}//编号int j = 0;for (j = 1; j <= max; j++){int k = 0;for (k = 1; k <= 10; k++){for (i = 1; i <= n; i++){if (j <= num[i]){//同一个学校隔位坐if (pre == i){id += 2;}else{//不同学校正常坐id += 1;}pre = i;pos[i][j][k] = id;}}}}//打印编号信息for (i = 1; i <= n; i++){printf("#%d\n", i);for (j = 1; j <= num[i]; j++){int k = 0;for (k = 1; k <= 10; k++){if (k != 10){printf("%d ", pos[i][j][k]);}else{printf("%d\n", pos[i][j][k]);}}}}return 0;
}

大致思路： 

1. 使用三维数组记录：每一个学校编号，每一个学校分配到的编号

注：每一个学校分配到的编号可以看成一个二维数组，行是该学校队伍的支数，列是一队的人数10

2. 分配编号:  以输入3
                                3 4 2  为例
 

    a. 分成最大队伍数轮

        分成四轮：第一轮给所有学校的第一支队伍分配编号

                          第二轮给所有学校的第二支队伍分配编号(若是有2支队伍）

                          第三轮给所有学校的第三支队伍分配编号(若是有3支队伍）

                          第四轮给所有学校的第四支队伍分配编号(若是有4支队伍）

     b. 每一轮：给所有学校的某一支队伍的10个位置编号

                        现有3个学校，学校编号为1，2，3

                         学校1：3支队伍，编号的二维数组，行为3，列为10

                         学校2：4支队伍，编号的二维数组，行为4，列为10

                         学校3：2支队伍，编号的二维数组，行为2，列为10

     c. 若是当前进行分配编号的学校与上一个分配编号的学校不同，则正常编号

          若是相同，则隔位编号

代码解读：

part 1：

   //输入各高校队伍数并求出最大的队伍数for (i = 1; i <= n; i++){scanf("%d", &num[i]);max = num[i] > max ? num[i] : max;}

所有学校的最大队伍数存储到max中 

part 2：

  //编号int j = 0;for (j = 1; j <= max; j++){int k = 0;for (k = 1; k <= 10; k++){for (i = 1; i <= n; i++){if (j <= num[i]){//同一个学校隔位坐if (pre == i){id += 2;}else{//不同学校正常坐id += 1;}pre = i;pos[i][j][k] = id;}}}}

1 编号的进行可以看成一个二维数组：行是最大队伍数（保证所有学校都能分配到编号），列是10

2 第一个for循环进行max次，每一次都给所有学校的某一支队伍（10个位置）编号  

编号之前需要判断当前的轮（代表所有学校要进行编号的第x支队伍）是否小于等于当前分配编号的学校的队伍数

若是满足条件，则可以编号

若是大于，则不进行编号，因为当前要分配编号的学校没有这支队伍的位置

3 若是当前进行分配编号的学校与上一个分配编号的学校不同，则正常编号

          若是相同，则隔位编号

  以如下案列为例：

输入样例：

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

总共进行4次循环，因为最大队伍数是4

第一次循环：给学校1，学校2，学校3的第一支队伍的10个位置分配编号

第二次循环：给学校1，学校2，学校3的第二支队伍的10个位置分配编号

第三次循环：给学校1，学校2，学校3的第三支队伍的10个位置分配编号

第四次循环：给学校1，学校2，学校3的第四支队伍的10个位置分配编号

但是：学校1能分配编号的共3支队伍，学校2能分配编号的共4支队伍，学校3能分配编号的共2支队伍，即学校1和2能够进行3轮，给自己的1，2，3的队伍编号，只有学校4能够进行第4轮给自己的第四支队伍编号 ，学校3只能进行两轮给自己的1，2的队伍编号

故而我们在编号之前需要进行判断：

if (j <= num[i])

j可以想象成二维数组的行，可以代表第几支队伍