C++에서 액세스할 때마다 최대값이 감소할 때 배열의 최대값

이 문제에서 배열 arr[]와 정수 M이 주어집니다. 우리의 임무는 C++에서 액세스할 때마다 최대값이 감소할 때 배열에서 최대값을 찾는 프로그램을 만드는 것입니다.

문제 설명

최대값을 찾기 위해 배열에서 maximumelement를 찾고 검색할 때마다 Mtimes만큼 감소시킵니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 :arr[] ={3, 6, 8, 9} M =2

출력 :17

설명

첫 번째 반복, 최대 =9, 합계 =9, 업데이트된 arr ={3, 6, 8, 8}

두 번째 반복, 최대 =8, 합계 =9+8 =17, 업데이트된 arr ={3, 6, 7, 8}

솔루션 접근 방식

간단한 해결책은 최대 요소가 루트인 최대 힙을 사용하는 것입니다. 그런 다음 루트를 팝하고 1로 줄인 다음 요소를 다시 삽입하십시오. 이것은 팝업 및 삽입이 M 번 수행됩니다. 각 팝 작업에 대해 요소를 sum 요소에 추가하고 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