用 Python 编写程序检查是否所有人都能得到座位

pythonserver side programmingprogramming更新于 2026/1/3 10:20:17

假设我们有一个数字 n，有 n 个人在寻找座位，我们还有一个位列表，其中 1 表示已经占用的座位，0 表示空座位。没有两个人可以坐在一起，所以我们必须检查所有 n 个人是否都能找到座位。

因此，如果输入为 n = 2 seat = [1, 0, 0, 0, 1, 0, 0]，则输出将为 True，因为他们可以坐在索引 2 和 6 处。

为了解决这个问题，我们将遵循以下步骤 −

在 seat 开头插入 0，在 seat 结尾插入 [0, 1]
res := 0, gap := 0
对于 seat 中的每个 i，执行
- 如果 i 与 0 相同，则
  - gap := gap + 1
- 否则当 gap > 0，则
  - res := res + floor of (gap - 1)/2
  - gap := 0
当 res >= n 时返回 true，否则返回 false

示例

让我们看看下面的实现以便更好地理解 −

def solve(n, seats):
   seats = [0] + seats + [0, 1]
   res = 0
   gap = 0
   for i in seats:
      if i == 0:
         gap += 1
      elif gap > 0:
         res += (gap - 1) // 2
         gap = 0
   return res >= n

n = 2
seats = [1, 0, 0, 0, 1, 0, 0]
print(solve(n, seats))