หา Maximum Cost ของ Array of Pairs เลือกได้สูงสุด K คู่ใน C++

โจทย์: กำหนด array of pairs A เลือกได้สูงสุด K คู่ Cost = (ผลรวม first elements) × (min ของ second elements ในคู่ที่เลือก) หา max cost

ตัวอย่าง: เลือก (4,8), (10,3), (3,6) → cost = (4+10+3) × 3 = 51 (K=3)

อัลกอริธึม: Sort + Greedy + Min-Heap (Set)

1. Sort pairs ตาม second value (ค่าที่จะเป็น min) ขึ้น
2. วนจากคู่ที่มี second ใหญ่สุดไปเล็กสุด (i = N-1..0):
   • นำ first value เข้า my_set (ordered by first)
   • เก็บ sum ของ first values ใน set
   • ถ้า size > K → ลบ first ที่น้อยที่สุดออก (my_set.begin())
   • คำนวณ cost = sum * A[i].second อัปเดต max

ตัวอย่างโค้ด C++

#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; // ordered by first
    sort(A.begin(), A.end(), compactor);
    for (int i = N-1; i >= 0; --i) {
        my_set.insert({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

Complexity

• Time: O(N log N) sort + O(N log K) set operations
• Space: O(K)