সি++-এ ম্যাক্সিমাম এলিমেন্ট অ্যাক্সেসের পর ডিক্রিমেন্ট করা যেন সর্বোচ্চ যোগফল হয়

সমস্যা বিবরণ

একটি অ্যারে arr[] এবং ইন্টিজার k দেওয়া আছে। k বার সর্বোচ্চ উপাদান বেছে নিতে হবে, তার মান যোগফলে যোগ করতে হবে, এবং সেই উপাদানটি ১ কমিয়ে দিতে হবে। সর্বোচ্চ যোগফল বের করতে হবে।

উদাহরণ: arr = {3,6,7,8,8}, k = 3

প্রক্রিয়া:

ম্যাক্স = ৮, যোগফল = ৮, অ্যারে = {3,6,7,7,8}
ম্যাক্স = ৮, যোগফল = ১৬, অ্যারে = {3,6,7,7,7}
ম্যাক্স = ৭, যোগফল = ২৩, অ্যারে = {3,6,6,7,7}

আউটপুট: 23

সমাধানের পদ্ধতি

ম্যাক্স হিপ (Priority Queue) ব্যবহার:

সব উপাদান ম্যাক্স হিপে পুশ করুন।
k বার লুপ চালান:
- রুট (ম্যাক্স) পপ করুন, যোগফলে যোগ করুন।
- maxVal - 1 হিপে পুশ করুন।
যোগফল রিটার্ন করুন।

টাইম কমপ্লেক্সিটি: O((n+k) log n)।

উদাহরণ কোড

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

long calcMaxSumDec(int arr[], int m, int n) {
    long maxSum = 0, maxVal;
    priority_queue<long> max_heap;
    for (int i = 0; i < n; i++) max_heap.push(arr[i]);
    for (int i = 0; i < m; i++) {
        maxVal = max_heap.top(); max_heap.pop();
        maxSum += maxVal;
        max_heap.push(maxVal - 1);
    }
    return maxSum;
}

int main() {
    int arr[] = {2, 3, 5, 4}, m = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << calcMaxSumDec(arr, m, n);
    return 0;
}