C++ में अधिकतम K युग्मों को चुनने वाले युग्मों की एक सरणी की अधिकतम लागत ज्ञात कीजिए

मान लीजिए कि हमारे पास जोड़े ए की एक सरणी है; हमें अधिकतम K युग्मों के चयन के लिए अधिकतम लागत ज्ञात करनी होगी। इस मामले में, जोड़े प्रकार के तत्वों की एक सरणी की लागत चयनित जोड़ी के पहले तत्वों के योग का उत्पाद है और चयनित जोड़े के दूसरे तत्वों में सबसे छोटा है। उदाहरण के तौर पर, यदि इन जोड़ियों को (4, 8), (10, 3) और (3, 6) चुना जाता है, तो K=3 के लिए लागत (4+10+3)*(3) =51 होगी।

इसलिए, यदि इनपुट ए =[(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 को क्रमबद्ध करें

• इनिशियलाइज़ करने के लिए मैं :=N-1, जब i>=0, अपडेट (i से 1 घटाएँ), करें -

  • एक जोड़ी बनाएं (ए [i], i का पहला तत्व) और my_set में डालें

  • योग:=योग + ए का पहला तत्व [i]

  • जबकि my_set> K का आकार, करें −

    • यह:=my_set का पहला तत्व

    • योग :=योग - इसमें से पहला

    • इसे my_set से हटाएं

  • रेस :=अधिकतम रेस और योग * ए का दूसरा [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