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

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

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

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

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

इसलिए, यदि इनपुट गुणवत्ता =[10,22,5], वेतन =[70,52,30] और के =2 की तरह है, तो आउटपुट 105.000 होगा। ऐसा इसलिए है क्योंकि हम पहले कर्मचारी को 70 और तीसरे कर्मचारी को 35 का भुगतान करेंगे।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• डेटा को q, w और r के साथ परिभाषित करें

• n :=गुणवत्ता का आकार

• n आकार के डेटा v की एक सरणी बनाएं

• इनिशियलाइज़ i :=0 के लिए, जब i

  • v का q[i] :=गुणवत्ता[i]

  • डब्ल्यू का वी[i] :=मजदूरी[i]

  • r का v[i] :=w का v[i] /q का v[i]

• r मानों के आधार पर सरणी v को क्रमबद्ध करें

• अस्थायी:=0

• योग :=0

• Ans :=inf

• एक प्राथमिकता कतार pq परिभाषित करें

• इनिशियलाइज़ i :=0 के लिए, जब i

  • यदि pq का आकार k के समान है, तो -

    • x :=pq का शीर्ष अवयव

    • योग :=योग - x

    • pq से तत्व हटाएं

  • यदि pq का आकार k-1 के समान है, तो -

    • Ans :=न्यूनतम (योग * r का v[i]) + w का v[i] और ans

  • योग :=योग + q का v[i]

  • 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