在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 婆婆高寿祝福语大全简短