C++で最大Kペアを選択するペアの配列の最大コストを見つけます

ペアAの配列があるとします。最大でKペアを選択するための最大コストを見つける必要があります。この場合、ペアタイプの要素の配列のコストは、選択されたペアの最初の要素の合計と、選択されたペアの2番目の要素の中で最小のものの積です。例として、これらのペアが選択された場合（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になります

これを解決するには、次の手順に従います-

• res：=0、sum =0

• N：=Aのサイズ

• my_set

  と呼ばれるペアの1つのセットを定義します

• 各ペアの2番目の値に基づいて配列Aを並べ替えます

• 初期化i：=N --1の場合、i> =0の場合、更新（iを1つ減らす）、実行-

  • ペアを作成し（A [i]、iの最初の要素）、my_setに挿入します

  • sum：=sum + A [i]

    の最初の要素

  • my_set> Kのサイズで、実行-

    • it：=my_setの最初の要素

    • sum：=sum-最初に

    • my_setから削除します

  • res：=resの最大値と合計*A [i]

    の2番目

• 解像度を返す

例

理解を深めるために、次の実装を見てみましょう-

#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