โปรแกรมนับจำนวนวิธีแจกเหรียญให้พนักงานใน Python

สมมติว่าเรามีสองรายการ coins และ salaries โดย coins[i] คือค่าเหรียญ i และ salaries[j] เป็นเงินเดือนขั้นต่ำของพนักงาน j มีเหรียญแต่ละประเภท 1 เหรียญ ต้องให้แต่ละพนักงาน 1 เหรียญ หาจำนวนวิธีการแจก (mod 10^9+7)

ตัวอย่าง: coins = [1, 2, 3], salaries = [1, 2] ผลลัพธ์คือ 4

ขั้นตอนการแก้ปัญหา

1. เรียง coins และ salaries
2. num_coins = len(coins), num_salaries = len(salaries)
3. สร้าง dp เป็นแผนที่
4. สำหรับแต่ละ salary ใน salaries:
   • ค้นหา index แรก idx ที่ coins[idx] >= salary ด้วย Binary Search
   • ถ้า idx == num_coins คืนค่า 0
   • dp[salary] = idx
5. res = 1
6. วนลูป i จาก num_salaries-1 ถึง 0:
   • salary = salaries[i], idx = dp[salary]
   • res *= (num_coins - idx + 1) - (num_salaries - i)
7. คืนค่า res % (10**9+7)

ตัวอย่างโค้ด Python

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, r = 0, 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))  # Output: 4

อินพุต / เอาต์พุต

Input: [1, 2, 3], [1, 2]

Output: 4