পাইথনে K জন কর্মী নিয়োগের ন্যূনতম খরচ খুঁজে বের করার প্রোগ্রাম

আমাদের একটি অ্যারে আছে quality প্রতিটি কর্মীর জন্য, আর একটি অ্যারে wage এবং একটি মান K। i-তম কর্মীর কোয়ালিটি quality[i] এবং ন্যূনতম বেতন আশা wage[i]। আমরা K জন কর্মী নিয়োগ করব একটি পেইড গ্রুপ তৈরি করতে। যখন আমরা K জন কর্মী নিয়োগ করব, তবে আমাদের নিচের নিয়ম অনুযায়ী বেতন দিতে হবে:

পেইড গ্রুপের প্রতিটি কর্মীকে অন্যদের সাথে কোয়ালিটি অনুপাতে বেতন দিতে হবে।
পেইড গ্রুপের প্রতিটি কর্মীকে অন্তত তাদের ন্যূনতম বেতন আশা দেওয়া হবে।

আমাদের উপরের শর্তগুলো পূরণ করে পেইড গ্রুপ তৈরি করতে ন্যূনতম টাকার পরিমাণ বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট quality = [10,22,5], wage = [70,52,30], K = 2 হলে আউটপুট হবে 105.000 কারণ আমরা প্রথম কর্মীকে ৭০ এবং তৃতীয় কর্মীকে ৩৫ টাকা দেব।

সমাধানের ধাপসমূহ

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