C ++中每次访问后最大减量时数组的最大值

在此问题中，给我们一个数组arr []和一个整数M。我们的任务是创建一个程序，以在C ++中每次访问后最大减量时从数组中查找最大值。

问题描述

为了找到最大值，我们将从数组中找到最大值，并在每次检索之后将其减小-1（M次）。

让我们举个例子来了解这个问题，

输入：arr [] = {3，6，8，9} M = 2

数量：17

说明

第一次迭代，最大值= 9，总和= 9，更新的arr = {3，6，8，8}

第2次迭代，最大值= 8，总和= 9 + 8 = 17，更新的arr = {3，6，7，8}

解决方法

一个简单的解决方案是使用max堆，该堆将在根目录具有max元素。然后弹出根，将其减小1，然后再次插入元素。弹出并插入M次。对于每个弹出操作，我们将元素添加到sum元素，并在M次迭代后打印总和。

示例

#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 maximumVal = heap.top();
      sumVal += maximumVal;
      heap.pop();
      heap.push(maximumVal - 1);
   }
   return sumVal;
}
int main() {
   int arr[] = { 3, 6, 8, 9};
   int M = 2;
   int N = sizeof(arr) / sizeof(arr[0]);
   cout<<"The maximum from array when the maximum decrements after every access is "<<getSum(arr, N,M);
}

输出结果

The maximum from array when the maximum decrements after every access is 17