मान लीजिए कि n इंजीनियर हैं। वे 1 से n तक गिने जाते हैं और हमारे पास दो सरणियाँ भी हैं:गति और दक्षता, यहाँ गति [i] और दक्षता [i] ith इंजीनियर के लिए गति और दक्षता का प्रतिनिधित्व करती है। हमें अधिकतम k इंजीनियरों से बनी टीम का अधिकतम प्रदर्शन खोजना होगा। उत्तर बहुत बड़ा हो सकता है इसलिए इसे मॉड्यूलो 10^9 + 7 लौटाएं।
यहां एक टीम का प्रदर्शन उनके इंजीनियरों की गति को उनके इंजीनियरों की न्यूनतम दक्षता से गुणा करने का योग है।
इसलिए, यदि इनपुट n =6, गति =[1,5,8,2,10,3], दक्षता =[9,7,2,5,4,3], k =2 जैसा है, तो आउटपुट 60 होगा, क्योंकि हमारे पास गति 10 और दक्षता 4 के साथ इंजीनियर और गति 5 और दक्षता 7 के साथ इंजीनियर का चयन करके टीम का अधिकतम प्रदर्शन है। यानी प्रदर्शन =(10 + 5) * मिनट (4, 7) =60 ।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
रिट:=0
-
एक 2डी सरणी को परिभाषित करें v
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
v के अंत में {e[i], s[i] } डालें
-
-
सरणी v को उल्टे क्रम में क्रमबद्ध करें
-
एक प्राथमिकता कतार pq परिभाषित करें
-
योग :=0
-
इनिशियलाइज़ i :=0 के लिए, जब i
-
यदि pq का आकार k के समान है, तो -
-
योग :=योग का शीर्ष तत्व - pq
-
pq से तत्व हटाएं
-
-
योग :=योग + वी[i, 1]
-
pq में v[i, 1] डालें
-
रिट :=अधिकतम रिट और योग * v[i, 0]
-
-
रिटर्न रिट मोड (1^9 + 7)
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxPerformance(int n, vector<int>& s, vector<int>& e, int k){
long long int ret = 0;
vector<vector<int> > v;
for (int i = 0; i < n; i++) {
v.push_back({ e[i], s[i] });
}
sort(v.rbegin(), v.rend());
priority_queue<int, vector<int>, greater<int> > pq;
long long int sum = 0;
for (int i = 0; i < n; i++) {
if (pq.size() == k) {
sum -= pq.top();
pq.pop();
}
sum += v[i][1];
pq.push(v[i][1]);
ret = max(ret, sum * v[i][0]);
}
return ret % (long long int)(1e9 + 7);
}
};
main(){
Solution ob;
vector<int> v = {1,5,8,2,10,3};
vector<int> v1 = {9,7,2,5,4,3};
cout << (ob.maxPerformance(6,v,v1,2));
} इनपुट
6, {1,5,8,2,10,3}, {9,7,2,5,4,3}, 2 आउटपुट
60