मान लीजिए हमारे पास जोड़ों का एक ऐरे A है; हमें अधिकतम K जोड़े चुनकर अधिकतम लागत खोजनी है। इस मामले में, जोड़ों के ऐरे प्रकार के तत्वों की लागत चयनित जोड़े के पहले तत्वों के योग और चयनित जोड़े के दूसरे तत्वों में सबसे छोटे के गुणनफल के बराबर है। उदाहरण के लिए, यदि ये जोड़े चुने गए हैं (4, 8), (10, 3) और (3, 6), तो लागत (4+10+3)*(3) = 51 होगी, K=3 के लिए।
उदाहरण के लिए, यदि इनपुट A = [(15, 5), (65, 25), (35, 20), (20, 5), (35, 20), (15, 18), (3, 8), (12, 17)], K = 4 है, तो आउटपुट 2700 होगा।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- रिजल्ट := 0, सम = 0
- N := A का आकार
- my_set नामक जोड़ों का एक सेट परिभाषित करें
- ऐरे A को प्रत्येक जोड़ी के दूसरे मान के आधार पर सॉर्ट करें
- i := N - 1 से 0 तक घटते हुए लूप करें:
- (A[i] का पहला तत्व, i) की एक जोड़ी बनाएं और my_set में डालें
- सम := सम + A[i] का पहला तत्व
- जब तक my_set का आकार > K:
- it := my_set का पहला तत्व
- सम := सम - it का पहला
- my_set से it को हटाएं
- रिजल्ट := रिजल्ट और सम * A[i] के दूसरे का अधिकतम
- रिजल्ट लौटाएं
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; bool compactor(const pair<int, int>& a,const pair<int, int>& b) { return (a.second < b.second); } int get_maximum_cost(vector<pair<int, int> > &A, int K){ int res = 0, sum = 0; int N = A.size(); set<pair<int, int>> my_set; sort(A.begin(), A.end(), compactor); for (int i = N - 1; i >= 0; --i) { my_set.insert(make_pair(A[i].first, i)); sum += A[i].first; while (my_set.size() > K) { auto it = my_set.begin(); sum -= it->first; my_set.erase(it); } res = max(res, sum * A[i].second); } return res; } int main() { vector<pair<int, int> > arr = {{ 15, 5}, { 65, 25}, { 35, 20}, { 20, 5}, { 35, 20}, { 15, 18}, { 3, 8 }, {12, 17}}; int K = 4; cout << get_maximum_cost(arr, K); } इनपुट
{{15, 5},{65, 25}, { 35, 20}, { 20, 5}, { 35, 20}, { 15, 18}, { 3, 8 }, {12, 17}}, 4 आउटपुट
2700
