用 Python 编写程序，找出可以满足多少转学请求

pythonserver side programmingprogramming更新于 2025/12/7 19:56:17

假设有 n 个宿舍房间，编号从 0 到 n-1。宿舍里的学生想转到另一个房间，他们提出了几个转学请求。宿舍座位没有空置，只有当另一个学生代替愿意转学的学生时，转学请求才会得到处理。因此，给定请求，我们必须找出可以满足多少个请求。

因此，如果输入为 n = 3，请求 = [[0,2],[1,0],[2,1]]，则输出将为 3。

0 号房间的学生转到 2 号房间。

1 号房间的学生转到 0 号房间。

2 号房间的学生转到 1 号房间。

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

对于 k 在请求大小范围到 -1 内，减少 1，执行
- 对于 c 在(0 到请求大小和 k)的所有组合中，执行
  - d := 一个大小为 n 的新数组，包含值0
  - 对于 c 中的每个 i，执行
    - d[requests[i, 0]] := d[requests[i, 0]] - 1
    - d[requests[i, 1]] := d[requests[i, 1]] + 1
  - 如果 d 中的任何项都不为真，则
    - 返回 k
返回 0

示例

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

from itertools import combinations
def solve(n, requests):
   for k in range(len(requests), 0, -1):
      for c in combinations(range(len(requests)), k):
         d = [0] * n
         for i in c:
            d[requests[i][0]] -= 1
            d[requests[i][1]] += 1
         if not any(d):
            return k
   return 0

print(solve(3, [[0,2],[1,0],[2,1]]))