Giả sử chúng ta có hai danh sách các số dương được gọi là tiền và tiền lương. Ở đây xu [i] cho biết giá trị của xu i và tiền lương [j] cho biết mức lương ít nhất cần trả cho công nhân j. Bây giờ, giả sử chúng ta có một đồng mỗi loại và chúng ta phải cung cấp cho mỗi công nhân đúng một đồng, chúng ta phải tính số cách chia đồng cho mỗi công nhân. Ở đây có hai cách khác nhau nếu một số công nhân nhận một loại tiền theo một cách nhưng một loại tiền khác theo cách khác. Nếu kết quả là rất lớn, kết quả trả về mod 10 ^ 9 + 7.
Vì vậy, nếu đầu vào là xu =[1, 2, 3], tiền lương =[1, 2], thì đầu ra sẽ là 4, như thể chúng ta không sử dụng đồng xu đầu tiên (giá trị 1), thì cả hai đồng xu đều có giá trị cho cả hai người lao động, vì vậy có hai cách để trả lương cho người lao động. Bây giờ nếu chúng ta sử dụng đồng xu đầu tiên, thì nó chỉ có thể được chuyển cho công nhân đầu tiên, và sau đó chúng tôi có thể sử dụng bất kỳ đồng nào còn lại để trả cho công nhân thứ hai. Vì vậy, có bốn cách.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- sắp xếp các đồng tiền trong danh sách và sắp xếp lương trong danh sách
- num_coins:=kích thước của tiền xu
- num_salaries:=quy mô tiền lương
- dp:=một bản đồ mới
- đối với mỗi mức lương trong tiền lương, thực hiện
- l:=0, r:=num_coins - 1
- idx:=num_coins
- trong khi l <=r, thực hiện
- m:=l + (r - l) / 2
- nếu xu [m]> =tiền lương, thì
- idx:=m
- r:=m - 1
- nếu không,
- l:=m + 1
- nếu idx giống như num_coins, thì
- trả về 0
- dp [lương]:=idx
- res:=1
- đối với tôi trong phạm vi num_salaries - 1 đến 0, giảm 1, thực hiện
- lương:=lương [i]
- idx:=dp [lương]
- res:=res * (num_coins - idx + 1) - (num_salaries - i)
- trả về bản sửa đổi res 10 ^ 9 + 7
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
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)) Đầu vào
[1, 2, 3],[1, 2]
Đầu ra
4