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

在这个问题中，我们得到了N个整数和一个整数m的数组arr []。我们的任务是创建一个程序，以在每次访问后最大减量时从数组中查找最大数。

问题描述-我们需要找到数组中最大元素的最大和，并将最大值减少一千次。

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

输入值

arr[] = {3, 6, 7, 8, 8}, k = 3

输出结果

说明

First iteration: array before = {3, 6, 7, 8, 8}, max = 8, sum = 8, array after update = {3, 6, 7, 7, 8}
Second iteration: array before = {3, 6, 7, 7, 8}, max = 8, sum = 8 + 8 = 16, array after update = {3, 6, 7, 7, 7}
Third iteration: array before = {3, 6, 7, 7, 7}, max = 7, sum = 16 + 7 = 23, array after update = {3, 6, 6, 7, 7}
Maximum sum = 23

解决方法

这个想法是找到数组的最大值，然后在添加到maxSum之后递减。重复此过程k次即可得到结果。

为了找到数组的最大元素，可以有多种方法，最有前途的一种方法是使用最大堆数据结构。

因此，我们将数组的所有元素插入到最大堆中，堆中的最大元素表示在其根部。我们将其删除，添加到maxSum并将（元素-1）插入到堆中。进行k次以获得所需的maxSum。

算法

初始化-maxSum = 0

步骤1-创建最大堆数据结构并将元素推入其中。

步骤2-为i-> 0到k循环并遵循设置3-5。

步骤3-取根元素maxVal = root并弹出它。

第4步-将maxVal添加到maxSum，maxSum + = maxVal

第5步-将更新的maxVal插入最大堆。

步骤6-返回maxSum。

该程序说明了我们解决方案的工作原理，

示例

#include <bits/stdc++.h>
using namespace std;
long calcMaxSumDec(int arr[], int m, int n) {
   long maxSum = 0;
   long 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();
      maxSum += maxVal;
      max_heap.pop();
      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<<"The maximums from array when the maximum decrements after every access is    "<<calcMaxSumDec(arr, m, n);
}

输出结果

The maximums from array when the maximum decrements after every access is 13