Chương trình đếm số cách phân phối đồng xu cho công nhân bằng Python

Cho danh sách coins (giá trị đồng xu) và salaries (lương tối thiểu mỗi công nhân). Mỗi loại đồng xu có một cái, mỗi công nhân nhận đúng một đồng xu. Đếm số cách phân phối sao cho mỗi công nhân nhận được đồng xu có giá trị ≥ lương của họ. Kết quả modulo 10^9+7.

Ví dụ: coins = [1, 2, 3], salaries = [1, 2] → 4.

Quy trình giải quyết

1. Sắp xếp coins và salaries.
2. Với mỗi salary, dùng tìm kiếm nhị phân tìm chỉ số idx nhỏ nhất sao cho coins[idx] >= salary.
3. Nếu không tìm thấy, trả về 0.
4. Tính toán số cách: duyệt ngược từ công nhân cuối, nhân dồn số lựa chọn khả dụng.
5. Trả về kết quả modulo 10^9+7.

Ví dụ mã nguồn

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) // 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

Đầu vào

[1, 2, 3], [1, 2]

Đầu ra

4