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

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

問題の説明

最大値を見つけるために、配列から最大要素を見つけ、取得するたびに-1、Mtimesずつ減らします。

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

入力 ：arr [] ={3、6、8、9} M =2

出力 ：17

説明

最初の反復、最大=9、合計=9、更新されたarr ={3、6、8、8}

2回目の反復、最大=8、合計=9 + 8 =17、更新されたarr ={3、6、7、8}

ソリューションアプローチ

簡単な解決策は、最大要素がルートにある最大ヒープを使用することです。次に、ルートをポップし、1ずつ減らしてから、要素を再度挿入します。これはポップで挿入はM回行われます。ポップ操作ごとに、要素を合計要素に追加し、M回の反復後に合計を出力します。

例

#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