Tối đa từ mảng khi giảm tối đa sau mỗi lần truy cập trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng arr [] và một số nguyên M. Nhiệm vụ của chúng ta là tạo một chương trình để tìm Cực đại từ mảng khi giá trị lớn nhất giảm sau mỗi lần truy cập trong C ++.

Mô tả vấn đề

Để tìm giá trị lớn nhất, chúng ta sẽ tìm giá trị tối đa từ mảng và sau mỗi lần truy xuất và giảm nó đi -1, Mtimes.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào :arr [] ={3, 6, 8, 9} M =2

Bỏ qua :17

Giải thích

Lần lặp đầu tiên, tối đa =9, sum =9, cập nhật arr ={3, 6, 8, 8}

Lần lặp thứ 2, tối đa =8, sum =9 + 8 =17, cập nhật arr ={3, 6, 7, 8}

Phương pháp tiếp cận giải pháp

Một giải pháp đơn giản là sử dụng đống tối đa sẽ có phần tử tối đa biến mất. Sau đó, bật phần gốc, giảm nó đi 1, sau đó chèn lại phần tử. Việc bật và chèn này được thực hiện M lần. Đối với mỗi phép toán bật lên, chúng tôi sẽ thêm phần tử vào phần tử sum và in ra tổng sau M lần lặp.

Ví dụ

#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);
}

Đầu ra

The maximum from array when the maximum decrements after every access is 17