पायथन में k वर्कर्स को हायर करने की न्यूनतम लागत खोजने का प्रोग्राम

मान लीजिए हमारे पास प्रत्येक अलग वर्कर के लिए quality नामक एक ऐरे है, और एक wages नामक ऐरे और एक मान K है। i-वें वर्कर की एक quality[i] और न्यूनतम वेतन अपेक्षा wage[i] है। हम K वर्कर्स को हायर करके एक पेड ग्रुप बनाना चाहते हैं। जब हम K वर्कर्स का ग्रुप हायर कर रहे होते हैं, तो हमें उन्हें निम्नलिखित नियमों के अनुसार भुगतान करना होगा:

पेड ग्रुप में प्रत्येक वर्कर को ग्रुप में दूसरों की तुलना में उनकी गुणवत्ता के अनुपात में भुगतान किया जाना चाहिए।
पेड ग्रुप में हर वर्कर को कम से कम उनकी न्यूनतम वेतन अपेक्षा का भुगतान किया जाना चाहिए।

हमें उपरोक्त शर्तों को पूरा करने वाले पेड ग्रुप को बनाने के लिए आवश्यक कम से कम पैसे ढूंढने हैं।

उदाहरण के लिए, यदि इनपुट quality = [10,22,5], wage = [70,52,30] और K = 2 है, तो आउटपुट 105.000 होगा क्योंकि हम पहले वर्कर को 70 और तीसरे वर्कर को 35 का भुगतान करेंगे।

हल करने के चरण

qr := एक नई सूची
quality और wage से प्रत्येक जोड़ी (q, w) के लिए:
- (w/q, q) को qr के अंत में जोड़ें
qr सूची को सॉर्ट करें।
cand := एक नई सूची, csum := 0
i को 0 से K - 1 तक लूप चलाएं:
- -qr[i][1] को हीप cand में डालें
- csum := csum + qr[i][1]
ans := csum * qr[K - 1][0]
idx को K से quality के आकार तक लूप चलाएं:
- -qr[idx][1] को हीप cand में डालें
- csum := csum + qr[idx][1] + heapq.heappop(cand)
- ans = min(ans, csum * qr[idx][0])
ans वापस करें।

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

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

इनपुट

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