C++プログラムでアクセスするたびに最大値が減少するときの配列からの最大値

この問題では、N個の整数と整数mの配列arr[]が与えられます。私たちのタスクは、アクセスのたびに最大値が減少したときに、配列から最大値を見つけるプログラムを作成することです。

問題の説明 −配列の最大要素の最大合計を見つけ、最大値を1k倍減らす必要があります。

問題を理解するために例を見てみましょう

入力

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