数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序中数组最大值在每次访问后递减
在这个问题中，我们得到一个包含N个整数的数组arr[]和一个整数m。我们的任务是创建一个程序来查找数组中的最大值，其中最大值在每次访问后递减。
问题描述 − 我们需要找到数组中最大元素的最大和，并将取出的最大值减少k次。
让我们通过一个例子来理解这个问题：
输入
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 = 根元素并将其弹出。
步骤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
更新于: 2020-12-22
113 次浏览
广告