Python程序：计算将硬币分配给工人的方法数

假设我们有两个正数列表，分别称为coins和salaries。其中coins[i]表示硬币i的值，salaries[j]表示支付给工人j所需的最低工资。现在假设每种类型的硬币只有一个，并且必须给每个工人正好一枚硬币，我们需要计算将硬币分配给每个工人的方法数。如果某个工人在一種方法中收到一种类型的硬币，而在另一种方法中收到另一种类型的硬币，则这两种方法不同。如果结果非常大，则返回结果模10^9+7。

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

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

• 对列表coins进行排序，并对列表salaries进行排序。
• num_coins := coins的大小。
• num_salaries := salaries的大小。
• dp := 一个新的映射。
• 对于salaries中的每个工资，执行以下操作：
  • 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。
• 对于从num_salaries - 1到0的范围内的i，递减1，执行以下操作：
  • salary := salaries[i]。
  • idx := dp[salary]。
  • res := res *(num_coins - idx + 1) -(num_salaries - i)。
• 返回res模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))

输入

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

输出

4

Arnab Chakraborty

更新于: 2020年10月20日

274 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习