K श्रमिकों को नियुक्त करने की न्यूनतम लागत C++ में

मान लीजिए N श्रमिक हैं। प्रत्येक श्रमिक का एक गुणवत्ता पैरामीटर है। i-वें श्रमिक की quality[i] और न्यूनतम मजदूरी अपेक्षा wage[i] है। अब हम K श्रमिकों को नियुक्त करके एक भुगतान समूह बनाना चाहते हैं। जब हम K श्रमिकों के समूह को नियुक्त करते हैं, तो हमें उन्हें निम्नलिखित नियमों के अनुसार भुगतान करना होगा:

भुगतान समूह में प्रत्येक श्रमिक को समूह में दूसरों की तुलना में उनकी गुणवत्ता के अनुपात में भुगतान किया जाना चाहिए।
भुगतान समूह में प्रत्येक श्रमिक को कम से कम उनकी न्यूनतम मजदूरी अपेक्षा का भुगतान किया जाना चाहिए।

हमें उपरोक्त शर्तों को पूरा करने वाले भुगतान समूह को बनाने के लिए आवश्यक न्यूनतम धनराशि ढूंढनी है।

उदाहरण के लिए, यदि quality = [10,22,5], wage = [70,52,30] और K = 2, तो आउटपुट 105.000 होगा।

हल करने का दृष्टिकोण

हम मजदूरी/गुणवत्ता अनुपात के आधार पर लालची दृष्टिकोण और प्रायोरिटी क्यू का उपयोग करते हैं:

प्रत्येक श्रमिक के लिए अनुपात r = wage/quality की गणना करें
श्रमिकों को अनुपात r के अनुसार सॉर्ट करें
सबसे बड़ी गुणवत्ता वाले K-1 श्रमिकों को ट्रैक करने के लिए मैक्स-हीप बनाए रखें
प्रत्येक श्रमिक को "कैप्टन" (उच्चतम अनुपात) के रूप में मानें
लागत = (K-1 श्रमिकों की गुणवत्ता का योग + कैप्टन की गुणवत्ता) * कैप्टन का अनुपात
न्यूनतम लागत ट्रैक करें

उदाहरण

#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; 
    } 
}; 

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