用 Python 编写一个程序来计算我们可以向工人分发硬币的方式数量

pythonserver side programmingprogramming更新于 2026/2/2 11:56:17

假设我们有两个正数列表，分别称为硬币和工资。这里 coins[i] 表示硬币 i 的价值，salaries[j] 表示支付给工人 j 所需的最低工资。现在假设每种硬币都有一枚，并且我们必须给每个工人一枚硬币，我们必须计算给每个工人分发硬币的方式数量。如果某个工人以一种方式收到一种硬币，而以另一种方式收到另一种硬币，则两种方式会有所不同。如果结果非常大，则返回结果 mod 10^9+7。

因此，如果输入为 coins = [1, 2, 3], salaries = [1, 2]，则输出将为 4，因为如果我们不使用第一个硬币(值 1)，那么两个硬币对两个工人都有效，因此有两种方式可以向工人支付工资。现在如果我们使用第一枚硬币，那么它只能给第一个工人，然后我们可以使用剩下的任何一枚硬币来支付给第二个工人。所以有四种方法。

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

对 coins 列表进行排序，并对 salaries 列表进行排序
num_coins := coins 的大小
num_salaries := salaries 的大小
dp := 一个新的 map
对于 salaries 中的每个 salary，执行
- l := 0, r := num_coins - 1
- idx := num_coins
- 当 l <= r 时，执行
  - m := l +(r - l) / 2
  - 如果 coins[m] >= salary，则
    - idx := m
    - r := m - 1
  - 否则，
    - l := m + 1
- 如果 idx 与 num_coins 相同，则
  - 返回 0
- dp[salary] := idx
res := 1
对于 i，范围为 num_salaries - 1 到 0，减少 1，执行
- salary := salaries[i]
- idx := dp[salary]
- res := res *(num_coins - idx + 1) -(num_salaries - i)
返回 res mod 10^9+7

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

示例

class Solution:
   def solve(self, coins, salaries):
      coins.sort()
      salaries.sort()
      num_coins = len(coins)
      num_salaries = len(salaries)
      dp = {}
      for salary in salaries:
         l = 0
         r = num_coins - 1
         idx = num_coins
         while l <= r:
            m = l + (r - l) // 2
            if coins[m] >= salary:
               idx = m
               r = m - 1
            else:
               l = m + 1
         if idx == num_coins:
            return 0
         dp[salary] = idx
      res = 1
      for i in range(num_salaries - 1, -1, -1):
         salary = salaries[i]
         idx = dp[salary]
         res *= (num_coins - idx + 1) - (num_salaries - i)
      return res % (10**9+7)
ob = Solution()
coins = [1, 2, 3]
salaries = [1, 2]
print(ob.solve(coins, salaries))