问题描述

请实现一个铁路购票系统的简单座位分配算法，来处理一节车厢的座位分配。

假设一节车厢有20排、每一排5个座位。为方便起见，我们用1到100来给所有的座位编号，第一排是1到5号，第二排是6到10号，依次类推，第20排是96到100号。

购票时，一个人可能购一张或多张票，最多不超过5张。如果这几张票可以安排在同一排编号相邻的座位，则应该安排在编号最小的相邻座位。否则应该安排在编号最小的几个空座位中（不考虑是否相邻）。

假设初始时车票全部未被购买，现在给了一些购票指令，请你处理这些指令。

输入格式

输入的第一行包含一个整数n，表示购票指令的数量。

第二行包含n个整数，每个整数p在1到5之间，表示要购入的票数，相邻的两个数之间使用一个空格分隔。

输出格式

输出n行，每行对应一条指令的处理结果。

对于购票指令p，输出p张车票的编号，按从小到大排序。

样例输入

4
2 5 4 2

样例输出

1 2
6 7 8 9 10
11 12 13 14
3 4

样例说明

1) 购2张票，得到座位1、2。

2) 购5张票，得到座位6至10。

3) 购4张票，得到座位11至14。

4) 购2张票，得到座位3、4。

评测用例规模与约定

对于所有评测用例，1 ≤ n ≤ 100，所有购票数量之和不超过100。

编程语言：Python

解题思想：

1.最开始想了几种办法，包括使用set和座位范围判断，但是思路都不是非常清楚

2.将100个座位按题目要求存放为20行5列的列表

3.共3种情况（只卖一张票、全相邻的票、非全相邻的票）

4.根据3种情况的优先级进行3个判断，符合条件则输出并把符合条件的座位置0并跳出循环

5.特别需要注意的样例点包括：100个购买指令（100次1张票），包含全相邻和非全相邻的情况

可进行的优化：重复搜索次数太多，可以从某个有票的位置开始进行搜索

时间复杂度:O(n^4)

最大数据量:100*20*5*5=50000

IDE代码如下:

"""
关键代码说明：
Seat[FitSeatRow[k]][FitSeatCol[k]] = 0      # 将该座位置为0表示不存在
FitSeatRow.clear(), FitSeatCol.clear()      # 将这一轮的座位信息清空
FitSeatRow.append(j), FitSeatCol.append(k)  # 保存该座位的行与列
"""
 
 
def Print():  # 输出的函数
    for k in range(Number[i]):
        if k != Number[i] - 1:
            print(Seat[FitSeatRow[k]][FitSeatCol[k]], end=" ")
        else:
            print(Seat[FitSeatRow[k]][FitSeatCol[k]])
        Seat[FitSeatRow[k]][FitSeatCol[k]] = 0
    FitSeatRow.clear(), FitSeatCol.clear()
 
 
Order = int(input())  # 输入购票指令的数量
Number = input().split()  # 购票指令列表
for i in range(Order):
    Number[i] = int(Number[i])
 
# 生成座位列表
Seat = [[0 for i in range(5)] for j in range(20)]
k = 1
for i in range(20):
    for j in range(5):
        Seat[i][j] = k
        k += 1
 
# 开始安排座位
FitSeatRow, FitSeatCol = list(), list()  # 存放符合条件的座位的行与列
for i in range(Order):
    if Number[i] == 1:  # 本轮只卖一张票
        for j in range(20):
            Count = 0  # 统计符合条件的座位数
            for k in range(5):
                if Seat[j][k] >= 1:  # 找到符合条件的座位
                    Count += 1
                    FitSeatRow.append(j), FitSeatCol.append(k)
                    break
                else:
                    continue
            if Count == 1:  # 跳出循环
                break
    else:  # 本轮至少卖两张票
        for j in range(20):
            Count = 1  # 统计符合条件的座位数，至少本身符合，因此初值不再为0
            for k in range(5):
                if Seat[j][k] + 1 == Seat[j][k + 1]:  # 相邻的座位都满足条件
                    Count += 1
                    FitSeatRow.append(j), FitSeatCol.append(k)
                    if Count == Number[i]:  # 满足条件的座位已经足够
                        FitSeatRow.append(j), FitSeatCol.append(k + 1)
                        break
                    else:  # 满足条件的座位仍不够，则继续寻找
                        continue
                elif Number[i] < 5 - k:  # 这个座位不满足条件，但这一排剩下的座位仍有可能满足条件
                    Count = 1
                    FitSeatRow.clear(), FitSeatCol.clear()
                    continue  # 继续在这一排座位寻找
                else:  # 这一排座位不可能满足条件
                    Count = 1
                    FitSeatRow.clear(), FitSeatCol.clear()
                    break  # 去下一排座位寻找
            if Count == Number[i]:
                break
    if Count < Number[i]:  # 遍历了所有座位，不存在都是相邻座位的情况，因此从头开始遍历，只要找到空位就安排
        Count = 0  # 统计符合条件座位的个数，因为不需要判断是否相邻，所以初值不再设为1
        for j in range(20):
            for k in range(5):
                if Seat[j][k] >= 1:
                    FitSeatRow.append(j), FitSeatCol.append(k)
                    Count += 1
                if Count == Number[i]:
                    break
            if Count == Number[i]:
                break
    Print()