在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
以上是 在C ++程序中每次访问后最大减量时数组的最大值 的全部内容， 来源链接： utcz.com/z/321463.html
