Chương trình tìm chi phí tối thiểu để thuê k người trong Python

Mô tả bài toán

Mỗi người có quality[i] và mức lương tối thiểu wage[i]. Thuê K người. Lương phải tỷ lệ với quality và >= wage[i]. Tìm tổng lương tối thiểu.

Ví dụ

quality = [10,22,5], wage = [70,52,30], K = 2 -> 105.0 (trả 70 cho người 1, 35 cho người 3).

Giải thuật

1. Tính tỷ lệ w/q cho mỗi người, sắp xếp theo tỷ lệ.
2. Chọn K người đầu tiên, dùng max-heap lưu quality (dạng âm).
3. Duyệt người tiếp theo: thêm vào heap, pop quality lớn nhất, cập nhật tổng quality và kết quả.

Triển khai Python

import heapq

def solve(quality, wage, K):
    qr = []
    for q, w in zip(quality, wage):
        qr.append([w / q, q])
    qr.sort()
    cand, csum = [], 0
    for i in range(K):
        heapq.heappush(cand, -qr[i][1])
        csum += qr[i][1]
    ans = csum * qr[K - 1][0]
    for idx in range(K, len(quality)):
        heapq.heappush(cand, -qr[idx][1])
        csum += qr[idx][1] + heapq.heappop(cand)
        ans = min(ans, csum * qr[idx][0])
    return ans

quality = [10, 22, 5]
wage = [70, 52, 30]
K = 2
print(solve(quality, wage, K))

Đầu vào

[10,22,5], [70,52,30], 2

Đầu ra

105