假设我们有两个正数列表，分别是硬币和薪水。这里coins [i]表示硬币i的值，而salary [j]表示支付工人j所需的最低工资。现在假设每种类型有一个硬币，并且必须给每个工人精确的一枚硬币，我们必须计算将硬币分配给每个工人的方式数量。如果某个工人以一种方式接收一种类型的硬币，但以另一种方式接收另一种类型的硬币，则两种方法是不同的。如果结果很大，则返回结果mod 10 ^ 9 + 7。
因此，如果输入像硬币= [1、2、3]，薪水= [1、2]，那么输出将为4，就像我们不使用第一个硬币（值1）一样，则两个硬币都是对两个工人都有效，因此有两种向工人付款的方式。现在，如果我们使用第一个硬币，那么它只能交给第一个工人，然后我们可以使用剩余硬币中的任何一个来支付第二个工人。因此，有四种方法。
为了解决这个问题，我们将遵循以下步骤-
对列表硬币进行排序，并对列表薪水进行排序
num_coins：=硬币大小
num_salaries：=薪金大小
dp：=新映射
对于薪水中的每个薪水，
返回0
m：= l +(r-l)/ 2
如果硬币[m]> =薪水，则
除此以外，
idx：= m
r：= m-1
l：= m +1
l：= 0，r：= num_coins-1
idx：= num_coins
当l <= r时
如果idx与num_coins相同，则
dp [salary]：= idx
res：= 1
对于范围num_salaries-1到0的i，减1，
薪水：=薪水[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))[1, 2, 3],[1, 2]
输出结果
4