基础算法题——天梯赛座位分配（化繁为简）

Bertha 。 2022-11-22 12:40 121阅读 0赞

#### [天梯赛座位分配][Link 1] ####

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

--------------------

第一眼看题目，以为是找规律的题目，一个学校一个学校的更新元素，我找了好久都没找到通用的规律…（菜是原罪）  
后来灵光一闪，其实我被题目误导了。

**只要直接以学校为行，学生人数为列，给每个学生进行编号即可**（原来这么简单，哎）。  
样例按上述方法进行编号可得  
![样例][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

#include<bits/stdc++.h>
    using namespace std;
    struct node{ 
    	int c;
    	int arr[150];
    }school[110];
    
    int main(){ 
    	int n, h=0;
    	cin>>n;
    	for(int i=1; i<=n; i++){ 
    		cin>>school[i].c;
    		h = max(h, school[i].c);
    	}
    	
    	int x=1;
    	for(int i=1; i<=h*10; i++){ 
    		for(int j=1; j<=n; j++){ 
    			if(i>school[j].c*10) continue;
    			school[j].arr[i] = x++;
    			if(i!=1&&school[j].arr[i-1]+1==school[j].arr[i]){ 
    				x++;
    				school[j].arr[i]++;
    			}
    		}
    	}
    	
    	for(int i=1; i<=n; i++){ 
    		printf("#%d\n", i);
    		for(int j=1; j<=school[i].c*10; j++){ 
    			cout<<school[i].arr[j];
    			if(j%10!=0) cout<<" ";
    			if(j%10==0)
    			cout<<endl;
    		}
    	}
    	
    	return 0;
    }

正所谓：大道至简，复杂的问题的原理是清晰的…

[Link 1]: https://pintia.cn/problem-sets/994805046380707840/problems/994805081289900032
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/bcf83de913a54323a35a714c49ed09b3.png