ধরুন আমাদের প্রতিটি ভিন্ন কর্মীর জন্য গুণ নামক একটি অ্যারে আছে, এবং মজুরি এবং একটি মান কে নামক আরেকটি অ্যারে আছে। i-তম কর্মীর একটি গুণমান[i] এবং একটি ন্যূনতম মজুরি প্রত্যাশা মজুরি[i] আছে। আমরা একটি পেইড গ্রুপ গঠনের জন্য K কর্মীদের নিয়োগ করতে চাই। যখন আমরা K কর্মীদের একটি গ্রুপ নিয়োগ করি, তখন আমাদের অবশ্যই তাদের নিম্নলিখিত নিয়ম অনুসারে অর্থ প্রদান করতে হবে:
-
বেতনভুক্ত গ্রুপের প্রতিটি কর্মীকে তাদের মানের অনুপাতে বেতন দেওয়া উচিত অন্যদের সাথে তুলনা করে।
-
বেতনভুক্ত গোষ্ঠীর প্রতিটি শ্রমিককে অবশ্যই তাদের ন্যূনতম মজুরি প্রত্যাশা অনুযায়ী প্রদান করতে হবে।
উপরোক্ত শর্তগুলি পূরণ করে একটি অর্থপ্রদানকারী গ্রুপ গঠনের জন্য আমাদের সর্বনিম্ন পরিমাণ অর্থ খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট গুণমান =[10,22,5], মজুরি =[70,52,30] এবং K =2 এর মত হয়, তাহলে আউটপুট হবে 105.000 কারণ আমরা প্রথম কর্মীকে 70 এবং 35 টাকা দেব। 3য় কর্মী।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
qr :=একটি নতুন তালিকা
-
গুণমান এবং মজুরি থেকে প্রতিটি জোড়ার (q, w) জন্য, করুন
-
qr
এর শেষে সন্নিবেশ করুন (w/q, q)
-
-
তালিকাটি সাজান qr
-
cand :=একটি নতুন তালিকা, csum :=0
-
আমি 0 থেকে K - 1 রেঞ্জের জন্য, কর
-
হিপ ক্যান্ডে -qr[i, 1] ঢোকান
-
csum :=csum + qr[i, 1]
-
-
উত্তর :=csum * qr[K - 1, 0]
-
idx-এর জন্য K রেঞ্জ থেকে মানের আকার, করুন
-
হিপ ক্যান্ডে -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
