Tìm chi phí tối đa của một mảng các cặp chọn nhiều nhất K cặp trong C ++

Giả sử chúng ta có một mảng các cặp A; chúng ta phải tìm chi phí tối đa để chọn nhiều nhất K cặp. Trong trường hợp này, chi phí của một mảng các phần tử loại cặp là tích của tổng các phần tử đầu tiên của cặp được chọn và nhỏ nhất trong số các phần tử thứ hai của các cặp được chọn. Ví dụ:nếu các cặp này được chọn (4, 8), (10, 3) và (3, 6), thì chi phí sẽ là (4 + 10 + 3) * (3) =51, cho K =3

Vì vậy, nếu đầu vào giống như A =[(15, 5), (65, 25), (35, 20), (20, 5), (35, 20), (15, 18), (3, 8) ), (12, 17)], K =4, thì đầu ra sẽ là 2700

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• res:=0, sum =0

• N:=kích thước của A

• Xác định một tập hợp các cặp được gọi là my_set

• sắp xếp mảng A dựa trên giá trị thứ hai của mỗi cặp

• để khởi tạo i:=N - 1, khi i> =0, cập nhật (giảm i đi 1), thực hiện -

  • tạo một cặp (phần tử đầu tiên của A [i], i) và chèn vào my_set

  • sum:=sum + phần tử đầu tiên của A [i]

  • trong khi kích thước của my_set> K, do -

    • it:=phần tử đầu tiên của my_set

    • sum:=sum - trước tiên của nó

    • xóa nó khỏi my_set

  • res:=tối đa của res và sum * giây của A [i]

• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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);
}

Đầu vào

{{15, 5},{65, 25}, { 35, 20}, { 20, 5}, { 35, 20}, { 15, 18}, { 3, 8
}, {12, 17}}, 4

Đầu ra

2700