একটি অ্যারে arr[] ও পূর্ণসংখ্যা M দেওয়া আছে। প্রতিবার অ্যারে থেকে সর্বোচ্চ মান বের করে যোগফলে যোগ করতে হবে এবং সেই মানটি ১ কমিয়ে আবার অ্যারেতে রাখতে হবে। এই কাজ M বার করলে সর্বোচ্চ যোগফল কত হবে?
উদাহরণ
arr[] = {3, 6, 8, 9}, M = 2
আউটপুট: 17
ব্যাখ্যা: ১ম বার: max=9, sum=9, arr={3,6,8,8}। ২য় বার: max=8, sum=17, arr={3,6,7,8}।
সমাধান: ম্যাক্স হিপ (Priority Queue)
- সব উপাদান ম্যাক্স হিপে পুশ করুন।
Mবার: টপ এলিমেন্ট পপ করুন, যোগফলে যোগ করুন, ১ বিয়োগ করে আবার পুশ করুন।- টাইম কমপ্লেক্সিটি: O((N+M) log N)
C++ প্রোগ্রাম
#include <bits/stdc++.h>
using namespace std;
int getSum(int arr[], int N, int M) {
int sumVal = 0;
priority_queue<int> heap;
for (int i = 0; i < N; i++) heap.push(arr[i]);
while (M--) {
int maxVal = heap.top();
sumVal += maxVal;
heap.pop();
heap.push(maxVal - 1);
}
return sumVal;
}
int main() {
int arr[] = {3, 6, 8, 9};
int M = 2, N = sizeof(arr)/sizeof(arr[0]);
cout << "The maximum sum is " << getSum(arr, N, M);
return 0;
}
আউটপুট: The maximum sum is 17
