数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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
更新于: 2020年10月20日
274 次浏览
广告