C++-এ পেয়ার অ্যারে থেকে সর্বোচ্চ Kটি পেয়ার বেছে নিয়ে ম্যাক্সিমাম কস্ট বের করা

সমস্যা

পেয়ার অ্যারে A এবং K দেওয়া। সর্বোচ্চ Kটি পেয়ার বেছে নিতে হবে যাতে কস্ট সর্বোচ্চ হয়। কস্ট = (বাছাইকৃত পেয়ারগুলোর প্রথম মানের যোগফল) × (বাছাইকৃত পেয়ারগুলোর দ্বিতীয় মানের মিনিমাম)।

অ্যালগরিদম: গ্রিডি + সেট

1. পেয়ারগুলো দ্বিতীয় মান (দ্বিতীয় এলিমেন্ট) অনুযায়ী সর্ট করুন।
2. সবচেয়ে বড় দ্বিতীয় মান থেকে শুরু করে পুনরাবৃত্তি করুন।
3. প্রথম মানগুলো একটি সেটে (অর্ডার্ড) রাখুন যাতে ছোট মানগুলো সহজে বাদ দেওয়া যায়।
4. সেটের সাইজ > K হলে সবচেয়ে ছোট প্রথম মান বাদ দিন।
5. প্রতিটি ধাপে sum * current_second ক্যালকুলেট করে ম্যাক্সিমাম আপডেট করুন।

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; // {first_value, index}
    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(); // smallest first value
            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); // 2700
}

আউটপুট

2700