type
status
date
slug
summary
category
password
tags
icon
在刷天梯赛练习题库的时候遇到了这道题，觉得很有意思🤔。虽然难度不大，但是也花了我不少时间去解决bug，原因之一可能是我的思路和其他人不一样，它们老是有一个用例未通过，弄了许久还是弄出来了，最好后心情舒畅。这是我的第一篇讲算法题的blog，希望能帮助到屏幕前的你和以后的自己😘。
题目描述
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 开始。
输入样例：
输入样例：
输出样例：
思路
我看了别人的题解，大部分都是用一个三维或者二维数组来逐个分配 各个高校 各个队伍 各个队员的座位号，然后输出，这样代码略长，可能不好理解。
我就在想，能不能直接一次循环每个高校，实时计算该高校的所有座位号然后输出呢，这样代码会减少很多，但是重点是掌握座位号分布的规律。
分析规律
我直接贴出一个正确运行的结果，方便分析规律。
首先，假设有n个高校，那么每个高校输出的领头一行都是#n。
因为每个高校至少有一支队伍，所以所有高校的第一支队伍的第一行都是从n开始，然后隔n个座位号，例如这里n=5，第三个高校第一队的座位号就是：3 3+5 3+5+5 …,每行10个位置。
所以我们可以用一个变量step（每个高校创建一次），来保存当前座位号到下一个队员的步长，
一共循环+=step 当前高校队伍数*10（也就是队员总数）次，就可以输出所有队员的位置了，所以需要一个数组team[n]来保存各高校的队伍数。
但是step不是一成不变的，这个时候就要开始找step的变化规律了，这个规律已找到，问题迎刃而解！
通过观察结果我们发现，每一行行内的输出值的step是始终不变的，step只有在换行的时候（从最后一个step到下一行第一个）或者是（新一行的第一个到第二个）才可能改变，因此用count来保存当前高校已经输出的队员数量，当count%10 == 0 或者 1时，对step进行一次变化。
注意：无论什么情况，step始终≥2，所以step的每一次变化之后都要再取max(2,step);
那么每一行的最后一个到下一行的第一个的step跟这一行的step的关系是什么呢？
通过观察发现，每当一个队伍（10人）输出完时，如果有x个输出顺序在当前高校之前（假如当前输出的高校是4，那么只看1-3高校的情况）并且队伍数量刚好等于当前高校已经输出的队伍数（count/10），那么step就要-=x；
直接看图吧，应该够清晰了，一句话就是：换行时的step变化，只看输出在当前高校之前的高校情况。
换行时的step变化已经解决了，那么新的一行（第一个到第二个开始）的step变化又是什么规律呢？
这个规律应该比较明显，一开始step为n是因为还有n支高校没有输出完毕，同理，当前高校已经输出了(count/n)行，那么这行的step就是 (n - 队伍数量小于等于(count/n)也就是分配完毕的高校数量)。
但是每次都要去便利所有高校的队伍数量，统计之后再step-=，这样效率不高，我们可以用一个数组teamCount[11],来保存队伍数量为i的高校数量teamCount[i]，这样后面查找起来更方便，遍历1-(count/n),如果teamCount不为0，说明存在队伍数量小于(count/n)已经有teamCount[i]的，直接step-=就行了。
上代码
- 作者:NotionNext
- 链接:https://lsnx.top/article/tian-ti-sai-zuo-wei-fen-pei
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。