当前位置:首页 » 《随便一记》 » 正文

PTA L1-049 天梯赛座位分配(详解)

1 人参与  2023年05月06日 16:41  分类 : 《随便一记》  评论

点击全文阅读


前言:内容包括:题目,代码实现,大致思路,代码解读

题目:

天梯赛每年有大量参赛队员,要保证同一所学校的所有队员都不能相邻,分配座位就成为一件比较麻烦的事情。为此我们制定如下策略:假设某赛场有 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 开始。

输入样例:

33 4 2

输出样例:

#11 4 7 10 13 16 19 22 25 2831 34 37 40 43 46 49 52 55 5861 63 65 67 69 71 73 75 77 79#22 5 8 11 14 17 20 23 26 2932 35 38 41 44 47 50 53 56 5962 64 66 68 70 72 74 76 78 8082 84 86 88 90 92 94 96 98 100#33 6 9 12 15 18 21 24 27 3033 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 若是当前进行分配编号的学校与上一个分配编号的学校不同,则正常编号

          若是相同,则隔位编号

  以如下案列为例:

输入样例:

33 4 2

输出样例:

#11 4 7 10 13 16 19 22 25 2831 34 37 40 43 46 49 52 55 5861 63 65 67 69 71 73 75 77 79#22 5 8 11 14 17 20 23 26 2932 35 38 41 44 47 50 53 56 5962 64 66 68 70 72 74 76 78 8082 84 86 88 90 92 94 96 98 100#33 6 9 12 15 18 21 24 27 3033 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可以想象成二维数组的行,可以代表第几支队伍 


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/61196.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1