剧院座位安排¶

共有$mn$个观众。现在要根据身高顺序来安排座位，从左到右、从前到后身高依次递增。例如：

-> 1 1 2
-> 2 3 4
-> 6 7 7

然而观众抵达剧院的顺序是不固定的。假设按照下列顺序到达（$h_i$代表第i个到达观众的身高）： $$ h_1,h_2,\cdots,h_{mn} $$

观众只能从每一行的最左侧进入，在进入的过程中每经过一个已经有人的座位会增加1点拥挤度。

问：拥挤度最低是多少？

例如输入：

3 1
9 8 10

三行一列，一共三个座位，三个人依次达到，拥挤度是0。

再如：

3 3
3 4 4 1 1 1 1 1 2

最终座位安排是：

1 1 1
1 1 2
3 4 4

第三行的拥挤度最少是2，身高为3的人先到达已经坐下，后面来了两个身高为4的人。应该优先坐到里面的位置，这样拥挤度是2。

其余的人最少拥挤度也是2。只有最后一个身高为2的人入座时会产生拥挤度。

所以最终的答案是4.

计算¶

分析¶

这其实是一个非常通俗的生活场景

不难发现，座位安排是固定的，可变的因素只有相同身高的人组内的座位分配。

例如：

1 1 1
1 1 2
3 4 4

身高为1的人有四个，他们可以任意选择位置。

而每一个到来的观众都有最优决策：优先选择最右侧的座位。

这样可以最小化后续的观众进入时的拥挤度，并且也不会带来任何额外的拥挤度，因为最里面的座位总要有人去坐，越早有人坐下对整体的拥挤度越有利。

例如按照到达顺序

3 4 4 1 1 1 1 1 2

第一个到达的1应该坐在第一排第三列的位置。

我们先求出每个身高可以选择的座位，按照列标号降序排列：

# height : position(row, col)

{1: [(0, 2), (0, 1), (1, 1), (0, 0), (1, 0)],
 2: [(1, 2)],
 3: [(2, 0)],
 4: [(2, 2), (2, 1)]}

然后我们来遍历观众到达的数组，每次都从可以选择的座位里安排最右侧的座位即可。

代码¶

class Seat:
    def __init__(self, n, m):
        # 初始化座位矩阵
        self.matrix = [[0] * m for _ in range(n)]
        # 拥挤度
        self.res = 0

    def walk_in(self, x, y):
        """直接模拟观众走入座位"""
        self.matrix[x][y] = 1
        self.res += sum(self.matrix[x][i] for i in range(y))

def f():
    sorted_h = sorted(heights)  # 对身高进行排序
    d = {}
    for i, h in enumerate(sorted_h):
        if h not in d:
            d[h] = []
        # 记录每个身高对应的座位号
        d[h].append((i // m, i % m))
    for h in d:
        # 按照列表递减的顺序
        d[h].sort(key=lambda x: x[1], reverse=True)  

    seat = Seat(n, m)  # 创建座位对象
    for h in heights:
        # 优先选择最右侧的座位
        row, col = d[h].pop(0)
        # 来宾入座
        seat.walk_in(row, col)
    return seat.res

优化¶

当然，现在我们的Seat.walk_in在计算拥挤度的时候比较低效，如果问题的规模特别大，可以通过一种叫做二维树状数组的数据结构来增速（这种数据结构对前缀和运算和插入操作都是$\mathcal{O}(\log n)$复杂度）。

小规模的问题就没必要了。

最后更新: 2025-06-17 22:23:29
创建日期: 2024-12-27 23:17:42

剧院座位安排¶

计算¶

分析¶

代码¶

优化¶

广告

评论