找到在 C++ 中最多选择 K 对的一组对的最大成本

假设我们有一个由对 A 组成的数组；我们必须找到最多选择 K 对的最大成本。在这种情况下，pair 类型元素数组的成本是所选对的第一个元素与所选对的第二个元素中最小的元素之和的乘积。例如，如果选择这些对 (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

在线示例

让我们看看以下实现以获得更好的理解 -

#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