在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
热门推荐
10 感谢韩语老师祝福语简短
11 升职文案高级祝福语简短
12 花童结婚祝福语大全简短
13 向国庆送祝福语简短
14 什么寄语简短祝福语女生
15 客户回礼祝福语大全简短
16 女孩生日祝福语简短创意
17 家长回复节日祝福语简短
18 给外婆敬酒祝福语简短