สมมติว่าเรามีตัวเลขบวกสองรายการที่เรียกว่าเหรียญและเงินเดือน ที่นี่ coins[i] หมายถึงมูลค่าของเหรียญ i และเงินเดือน[j] หมายถึงจำนวนเงินเดือนที่น้อยที่สุดที่ต้องจ่ายให้กับคนงาน j สมมติว่าเรามีเหรียญหนึ่งเหรียญต่อประเภท และเราต้องให้เหรียญเดียวแก่คนงานแต่ละคน เราต้องคำนวณจำนวนวิธีที่จะให้เหรียญแก่คนงานแต่ละคน มีสองวิธีที่แตกต่างกันหากคนงานบางคนได้รับเหรียญประเภทหนึ่ง แต่ได้รับเหรียญประเภทอื่นในอีกทางหนึ่ง หากผลลัพธ์มีขนาดใหญ่มาก ให้ผลลัพธ์กลับ mod 10^9+7.
ดังนั้นหากอินพุตเป็นเหมือนเหรียญ =[1, 2, 3] เงินเดือน =[1, 2] ผลลัพธ์จะเป็น 4 ราวกับว่าเราไม่ได้ใช้เหรียญแรก (ค่า 1) ดังนั้นทั้งสองเหรียญจะเป็น ถูกต้องสำหรับคนงานทั้งสอง ดังนั้นจึงมี 2 วิธีในการจ่ายเงินให้กับคนงาน ตอนนี้ถ้าเราใช้เหรียญแรก มันก็จะไปหาคนงานคนแรกเท่านั้น จากนั้นเราก็สามารถใช้เหรียญที่เหลืออันใดอันหนึ่งเพื่อจ่ายคนงานคนที่สองได้ มีสี่วิธี
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- เรียงลำดับรายการเหรียญ และเรียงลำดับรายการเงินเดือน
- num_coins :=ขนาดของเหรียญ
- num_salaries :=ขนาดของเงินเดือน
- dp :=แผนที่ใหม่
- สำหรับแต่ละเงินเดือนในเงินเดือน ทำ
- l :=0, r :=num_coins - 1
- idx :=num_coins
- ในขณะที่ l <=r ทำ
- m :=l +(r - l) / 2
- ถ้า coins[m]>=เงินเดือน แล้ว
- idx :=ม
- r :=m - 1
- มิฉะนั้น
- l :=m + 1
- ถ้า idx เหมือนกับ num_coins แล้ว
- คืน 0
- dp[เงินเดือน] :=idx
- res :=1
- สำหรับฉันในช่วง num_salaries - 1 ถึง 0, ลดลง 1 ทำ
- เงินเดือน :=เงินเดือน[i]
- idx :=dp[เงินเดือน]
- 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
