ধরুন N শ্রমিক আছে। প্রতিটি কর্মীর মানের প্যারামিটার আছে। i-th কর্মী একটি গুণমান [i] এবং একটি ন্যূনতম মজুরি প্রত্যাশা মজুরি [i] আছে. এখন আমরা একটি পেইড গ্রুপ গঠনের জন্য K কর্মীদের নিয়োগ দিতে চাই। যখন আমরা K কর্মীদের একটি দল নিয়োগ করি, তখন আমাদের অবশ্যই তাদের নিম্নলিখিত নিয়ম অনুসারে অর্থ প্রদান করতে হবে −
-
বেতনভুক্ত গ্রুপের প্রতিটি কর্মীকে তাদের মানের অনুপাতে বেতন দেওয়া উচিত অন্যদের সাথে তুলনা করে।
-
বেতনভুক্ত গোষ্ঠীর প্রতিটি শ্রমিককে অবশ্যই তাদের ন্যূনতম মজুরি প্রত্যাশা অনুযায়ী প্রদান করতে হবে।
উপরোক্ত শর্তগুলি পূরণ করে একটি অর্থপ্রদানকারী গ্রুপ গঠনের জন্য আমাদের সর্বনিম্ন পরিমাণ অর্থ খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট মান =[10,22,5], মজুরি =[70,52,30] এবং K =2 এর মত হয়, তাহলে আউটপুট হবে 105.000। কারণ আমরা প্রথম কর্মীকে 70 টাকা এবং তৃতীয় কর্মীকে 35 টাকা দেব৷
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
q, w এবং r
দিয়ে ডেটা সংজ্ঞায়িত করুন -
n :=মানের আকার
-
n
আকারের ডেটা v এর একটি অ্যারে তৈরি করুন -
আরম্ভ করার জন্য i :=0, যখন i
-
v[i] এর q :=গুণমান[i]
-
w এর v[i] :=মজুরি[i]
-
r এর v[i] :=w এর v[i] /q এর v[i]
-
-
r মানের উপর ভিত্তি করে অ্যারে v সাজান
-
তাপমাত্রা :=0
-
যোগফল :=0
-
উত্তর :=inf
-
একটি অগ্রাধিকার সারি pq
সংজ্ঞায়িত করুন -
আরম্ভ করার জন্য i :=0, যখন i
-
যদি pq এর আকার k এর সমান হয়, তাহলে −
-
x :=pq
এর শীর্ষ উপাদান -
যোগফল :=যোগফল - x
-
pq
থেকে উপাদান মুছুন
-
-
যদি pq এর আকার k - 1 এর সমান হয়, তাহলে −
-
উত্তর :=সর্বনিম্ন (v[i] এর যোগফল * r) + w এর v[i] এবং উত্তর
-
-
যোগফল :=যোগফল + v[i]
এর q -
pq
-এ v[i] এর q সন্নিবেশ করান
-
-
উত্তর ফেরত দিন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Data {
double q, w, r;
};
class Solution {
public:
static bool cmp(Data a, Data b) { return a.r < b.r; }
double mincostToHireWorkers(vector<int> &quality, vector<int>
&wage, int k) {
int n = quality.size();
vector<Data> v(n);
for (int i = 0; i < n; i++) {
v[i].q = quality[i];
v[i].w = wage[i];
v[i].r = v[i].w / v[i].q;
}
sort(v.begin(), v.end(), cmp);
double temp = 0;
double sum = 0;
double ans = INT_MAX;
priority_queue<int> pq;
for (int i = 0; i < n; i++) {
if (pq.size() == k) {
double x = pq.top();
sum -= x;
pq.pop();
}
if (pq.size() == k - 1) {
ans = min((sum * v[i].r) + v[i].w, ans);
}
sum += v[i].q;
pq.push(v[i].q);
}
return ans;
}
};
main(){
Solution ob;
vector<int> v = {10,22,5}, v1 = {70,52,30};
cout << (ob.mincostToHireWorkers(v, v1, 2));
} ইনপুট
{10,22,5}
{70,52,30}
2 আউটপুট
105
