मान लीजिए कि हमारे पास प्रत्येक अलग-अलग कार्यकर्ता के लिए गुणवत्ता नामक एक सरणी है, और एक और सरणी है जिसे मजदूरी कहा जाता है और एक मूल्य K है। i-th कार्यकर्ता के पास एक गुणवत्ता [i] और न्यूनतम मजदूरी अपेक्षा मजदूरी [i] है। हम एक सशुल्क समूह बनाने के लिए K कार्यकर्ताओं को काम पर रखना चाहते हैं। जब हम K कर्मचारियों के एक समूह को काम पर रख रहे हैं, तो हमें उन्हें निम्नलिखित नियमों के अनुसार भुगतान करना होगा:
-
सशुल्क समूह के प्रत्येक कर्मचारी को भुगतान किए गए समूह में अन्य लोगों के साथ तुलना करके उनकी गुणवत्ता के अनुपात में भुगतान किया जाना चाहिए।
-
सशुल्क समूह के प्रत्येक कर्मचारी को कम से कम उनकी न्यूनतम वेतन अपेक्षा का भुगतान किया जाना चाहिए।
हमें उपरोक्त शर्तों को पूरा करने वाला एक भुगतान समूह बनाने के लिए आवश्यक न्यूनतम राशि का पता लगाना होगा।
इसलिए, यदि इनपुट गुणवत्ता =[10,22,5], वेतन =[70,52,30] और के =2 की तरह है, तो आउटपुट 105.000 होगा क्योंकि हम पहले कार्यकर्ता को 70 और कर्मचारियों को 35 का भुगतान करेंगे। तीसरा कार्यकर्ता।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
qr :=एक नई सूची
-
गुणवत्ता और वेतन से प्रत्येक जोड़ी (क्यू, डब्ल्यू) के लिए, करें
-
qr के अंत में (w/q, q) डालें
-
-
सूची qr को क्रमबद्ध करें
-
कैंड:=एक नई सूची, सीएसयूएम:=0
-
मैं के लिए 0 से के -1 की सीमा में, करो
-
-qr[i, 1] हीप कैंड में डालें
-
सीएसयूएम:=सीएसयूएम + क्यूआर [i, 1]
-
-
उत्तर:=सीएसयूएम * क्यूआर [के - 1, 0]
-
K से गुणवत्ता के आकार के idx के लिए, करें
-
-qr[i, 1] हीप कैंड में डालें
-
csum :=csum + qr[idx, 1] + हीप कैंड से शीर्ष तत्व और इसे हीप से हटा दें
-
ans =न्यूनतम उत्तर और (csum * qr[idx][0])
-
-
वापसी उत्तर
उदाहरण
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें
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
आउटपुट
105