सी++ में उनके प्रदर्शन के आधार पर कर्मचारियों को भुगतान की जाने वाली अंतिम राशि का पता लगाने के लिए कार्यक्रम

मान लीजिए कि हमारे पास समान लंबाई की संख्याओं की दो सूचियां हैं जिन्हें प्रदर्शन और लागत कहा जाता है। और हमारे पास एक और संख्या k भी है। ये इंगित करते हैं कि प्रत्येक कार्यकर्ता मैं प्रदर्शन [i] स्तर पर प्रदर्शन करता हूं और इसमें कम से कम लागतें [i] लगती हैं। हमें k कर्मचारियों को काम पर रखने के लिए न्यूनतम लागत का पता लगाना होगा, यह भी दिया गया है कि कर्मचारियों को समूह के अन्य कर्मचारियों की तुलना में उनके प्रदर्शन के अनुपात में भुगतान किया जाएगा।

इसलिए, यदि इनपुट प्रदर्शन की तरह है =[5, 3, 2] लागत =[100, 5, 4] k =2, तो आउटपुट 10 होगा, क्योंकि हम emp1 और emp2 का चयन कर सकते हैं। उन्हें कम से कम 5 + 4 =9 राशि का भुगतान करना होगा। लेकिन emp1 emp2 से 1.5 गुना बेहतर प्रदर्शन करता है, इसलिए उसे कम से कम 1.5 * 4 =6 का भुगतान किया जाना चाहिए। तो कुल मिलाकर उन्हें 6 + 4 =10 मिलेगा।

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

n :=c का आकार
n आकार की एक सरणी seq परिभाषित करें
seq को 0 से n−1 तक के मानों से भरें
इन मानदंडों के आधार पर सरणी seq को सॉर्ट करें (c[i] * p[j]
उत्तर :=inf, psum :=0
प्राथमिकता कतार pq परिभाषित करें
इनिशियलाइज़ i :=0 के लिए, जब i
- idx :=seq[i]
- p[idx] को pq में डालें
- psum :=psum + p[idx]
- यदि pq> k का आकार है, तो -
  - psum :=psum - pq का शीर्ष अवयव
  - pq से शीर्ष तत्व हटाएं
- अगर मैं>=k − 1, तो −
  - उत्तर:=न्यूनतम उत्तर और (c[idx] / p[idx] * psum)
वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

#include <bits/stdc++.h>
using namespace std;
double solve(vector<int>& p, vector<int>& c, int k) {
   int n = c.size();
   vector<int> seq(n);
   for (int i = 0; i < n; ++i)
   seq[i] = i;
   sort(seq.begin(), seq.end(), [&](int i, int j) { return c[i] *
   p[j] < c[j] * p[i]; });
   double ans = INT_MAX, psum = 0;
   priority_queue<int> pq;
   for (int i = 0; i < n; ++i) {
      int idx = seq[i];
      pq.emplace(p[idx]);
      psum += p[idx];
      if (pq.size() > k) {
         psum −= pq.top();
         pq.pop();
      }
      if (i >= k − 1)
      ans = min(ans, (double)c[idx] / p[idx] * psum);
   }
   return ans;
}
int main(){
   vector<int> performance = {5, 3, 2};
   vector<int> costs = {100, 5, 4};
   int k = 2;
   cout << solve(performance, costs, k);
}

इनपुट

{5, 3, 2}, {100, 5, 4}, 2