Chi phí tối đa chọn tối đa K cặp từ mảng cặp trong C++

Cho mảng cặp A = [(first, second), ...]. Chi phí chọn tập con S: (sum first) * (min second trong S). Tối đa hóa chi phí với tối đa K cặp.

Ví dụ

A = [(15,5), (65,25), (35,20), (20,5), (35,20), (15,18), (3,8), (12,17)], K=4

Output: 2700

Thuật toán tham lam + Set

• Sắp xếp cặp theo second tăng dần.
• Duyệt từ cuối (second lớn nhất), dùng multiset lưu first lớn nhất.
• Giữ tối đa K phần tử trong set (xóa first nhỏ nhất khi vượt K).
• Tính chi phí tại mỗi bước: sum_first * current_second.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

bool cmp(const pair<int,int>& a, const pair<int,int>& b) {
    return a.second < b.second;
}

int maxCost(vector<pair<int,int>>& A, int K) {
    sort(A.begin(), A.end(), cmp);
    multiset<int> ms; // lưu first
    long long sum = 0, res = 0;
    
    for (int i = A.size()-1; i >= 0; --i) {
        ms.insert(A[i].first);
        sum += A[i].first;
        if (ms.size() > K) {
            sum -= *ms.begin(); // xóa first nhỏ nhất
            ms.erase(ms.begin());
        }
        res = max(res, sum * (long long)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}
    };
    cout << maxCost(arr, 4); // 2700
    return 0;
}

Kết quả

2700

Giải thích: Khi duyệt second giảm dần, second hiện tại là min trong tập chọn. Giữ K first lớn nhất để tối đa tổng.