在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 儿童毕业祝福语 简短6
14 开工仪式横幅祝福语简短
15 孩子日常祝福语大全简短
16 清晨寄语诗句祝福语简短
17 结婚送亲认亲祝福语简短
18 虎年喝酒拜年祝福语简短