Python程序：计算可满足的转让请求数量

Python 服务器端编程编程

假设有n个宿舍房间，编号从0到n-1。宿舍里的学生想要换房间，他们为此提出了几个请求。没有空余的宿舍床位，只有当另一个学生替换想要搬迁的学生时，才会处理转让请求。因此，给定这些请求，我们必须找出可以满足多少个请求。

例如，如果输入为n = 3，requests = [[0,2],[1,0],[2,1]]，则输出为3。

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

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

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

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

对于k从requests大小-1到0循环递减，执行：
- 对于所有(0到requests大小和k)的组合c，执行：
  - d := 一个大小为n，值为0的新数组
  - 对于c中的每个i，执行：
    - d[requests[i, 0]] := d[requests[i, 0]] - 1
    - d[requests[i, 1]] := d[requests[i, 1]] + 1
  - 如果d中的所有元素都不为真（即都为0），则
    - 返回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]]))

输入

3, [[0,2],[1,0],[2,1]]

输出

Arnab Chakraborty

更新于：2021年10月7日

63 次浏览

开启您的职业生涯

完成课程获得认证

开始学习