परिचय
मान लीजिए हमारे पास समान लंबाई की दो संख्या सूचियाँ हैं जिन्हें performance और costs कहा जाता है। और हमारे पास एक और संख्या k है। ये इंगित करते हैं कि प्रत्येक कर्मचारी i performance[i] स्तर पर प्रदर्शन करता है और इसकी लागत कम से कम costs[i] है। हमें k कर्मचारियों को हायर करने की न्यूनतम लागत ढूंढनी है, यह देखते हुए कि कर्मचारियों को समूह में अन्य कर्मचारियों की तुलना में उनके प्रदर्शन के अनुपात में भुगतान किया जाएगा।
तो, यदि इनपुट performance = [5, 3, 2], costs = [100, 5, 4], k = 2 है, तो आउटपुट 10 होगा, क्योंकि हम emp1 और emp2 चुन सकते हैं। उन्हें कम से कम 5 + 4 = 9 राशि का भुगतान किया जाना चाहिए। लेकिन emp1, emp2 से 1.5 गुना बेहतर प्रदर्शन करता है, इसलिए उसे कम से कम 1.5 * 4 = 6 भुगतान किया जाना चाहिए। तो कुल मिलाकर उन्हें 6 + 4 = 10 मिलेगा।
समाधान दृष्टिकोण
कर्मचारियों को cost/performance अनुपात के आधार पर सॉर्ट करें। फिर एक मैक्स-हीप का उपयोग करके शीर्ष k प्रदर्शनकर्ताओं को ट्रैक करें। प्रत्येक कर्मचारी को "कैप्टन" मानकर न्यूनतम लागत की गणना करें।
उदाहरण कोड
#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);
return 0;
}
इनपुट
{5, 3, 2}, {100, 5, 4}, 2
आउटपुट
10
निष्कर्ष
यह लालची (greedy) + हीप दृष्टिकोण O(n log n) समय में इष्टतम समाधान ढूंढता है। कर्मचारियों को इकाई प्रदर्शन लागत के आधार पर सॉर्ट किया जाता है। यदि आपके कोई प्रश्न हैं, तो कमेंट सेक्शन में पूछें।
