C++에서 최대 K 쌍을 선택하는 쌍 배열의 최대 비용 찾기

A 쌍의 배열이 있다고 가정합니다. 최대 K 쌍을 선택하기 위한 최대 비용을 찾아야 합니다. 이 경우 쌍 유형 요소의 배열 비용은 선택한 쌍의 첫 번째 요소와 선택한 쌍의 두 번째 요소 중 가장 작은 요소의 합을 곱한 값입니다. 예를 들어, 이러한 쌍이 (4, 8), (10, 3) 및 (3, 6)으로 선택되면 비용은 K=3인 경우 (4+10+3)*(3) =51이 됩니다.

따라서 입력이 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 정렬

• initialize i :=N - 1의 경우, i>=0일 때 업데이트(i를 1만큼 감소), −

  • 쌍을 만들고(A[i], i의 첫 번째 요소) my_set에 삽입

  • 합계 :=합계 + A[i]의 첫 번째 요소

  • my_set의 크기가 K인 동안 −

    • it :=my_set의 첫 번째 요소

    • 합계 :=합계 - 첫 번째

    • my_set에서 삭제

  • res :=최대 res 및 sum * 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