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)을 다시 힙에 삽입합니다. 원하는 maxSum을 얻으려면 이 작업을 k번 수행하십시오.

알고리즘

초기화 - 최대 합계 =0

1단계 − 최대 힙 데이터 구조를 만들고 여기에 요소를 푸시합니다.

2단계 − i -> 0에서 k에 대해 루프하고 세트 3 - 5를 따릅니다.

3단계 − 루트 요소인 maxVal =루트를 가져와 팝니다.

4단계 - maxSum에 maxVal 추가, 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