数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 中数组的最大值，每次访问后最大值递减
在这个问题中，我们给定一个数组 arr[] 和一个整数 M。我们的任务是创建一个程序，在 C++ 中找到数组中的最大值，并且每次访问后最大值递减。
问题描述
为了找到最大值，我们将从数组中找到最大元素，并在每次检索后将其减少 -1，进行 M 次。
让我们举个例子来理解这个问题：
输入: arr[] = {3, 6, 8, 9} M = 2
输出:17
解释
第 1 次迭代，最大值 = 9，总和 = 9，更新后的数组 = {3, 6, 8, 8}
第 2 次迭代，最大值 = 8，总和 = 9+8 = 17，更新后的数组 = {3, 6, 7, 8}
解决方案方法
一个简单的解决方案是使用最大堆，它将在根节点处具有最大元素。然后弹出根节点，将其减少 1，然后再次插入元素。此弹出和插入操作执行 M 次。对于每个弹出操作，我们将元素添加到 sum 元素，并在 M 次迭代后打印 sum。
示例
#include <bits/stdc++.h>
using namespace std;
int getSum(int arr[], int N, int M) {
int sumVal = 0;
priority_queue<int> heap;
for (int i = 0; i < N; i++)
heap.push(arr[i]);
while (M--) {
int maximumVal = heap.top();
sumVal += maximumVal;
heap.pop();
heap.push(maximumVal - 1);
}
return sumVal;
}
int main() {
int arr[] = { 3, 6, 8, 9};
int M = 2;
int N = sizeof(arr) / sizeof(arr[0]);
cout<<"The maximum from array when the maximum decrements after every access is "<<getSum(arr, N,M);
}输出
The maximum from array when the maximum decrements after every access is 17
更新于: 2020-10-09
53 次查看
广告