C++-এ K ওয়ার্কার नियোগের ন্যূনতম খরচ

সমস্যা বিবরণ

Nটি ওয়ার্কার, প্রতিটির quality[i] এবং wage[i] দেওয়া থাকলে। Kটি ওয়ার্কার নিয়োগ করতে হবে যাতে: ১) পেমেন্ট কোয়ালিটির অনুপাতে হয়, ২) প্রত্যেকে তার এক্সপেক্টেড wage পায়। ন্যূনতম টোটাল খরচ বের করতে হবে।

উদাহরণ

quality = [10,22,5], wage = [70,52,30], K = 2 → আউটপুট = 105.0 (১ম ওয়ার্কার ৭০, ৩য় ওয়ার্কার ৩৫)

সমাধান পদ্ধতি

• ratio = wage/quality দিয়ে সর্ট করা হয়।
• প্রায়োরিটি কিউ (Max Heap) দিয়ে K-১টি সবচেয়ে ছোট কোয়ালিটি রাখা হয়।
• প্রতিটি ওয়ার্কারকে ক্যাপ্টেন ধরে বাকি K-১টি বেছে নেওয়া হয়।
• খরচ = (sum of quality) * ratio + wage[captain]।

C++ বাস্তবায়ন

#include <bits/stdc++.h>
using namespace std;

struct Data { double q, w, r; };

class Solution {
    static bool cmp(Data a, Data b) { return a.r < b.r; }
    
public:
    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 sum = 0, ans = INT_MAX;
        priority_queue<int> pq;
        
        for (int i = 0; i < n; i++) {
            if (pq.size() == k) {
                sum -= pq.top();
                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;
    }
};

int main() {
    Solution ob;
    vector<int> v = {10,22,5}, v1 = {70,52,30};
    cout << ob.mincostToHireWorkers(v, v1, 2);
    return 0;
}

ইনপুট ও আউটপুট

ইনপুট: {10,22,5} {70,52,30} 2

আউটপুট: 105