Cực đại từ mảng khi số tối đa giảm sau mỗi lần truy cập trong Chương trình C ++

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

Mô tả sự cố - Chúng ta cần tìm tổng lớn nhất của các phần tử lớn nhất của mảng và giảm giá trị lớn nhất được lấy đi một k lần.

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

Đầu vào

arr[] = {3, 6, 7, 8, 8}, k = 3

Đầu ra

Giải thích

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

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

Ý tưởng là tìm giá trị tối đa của mảng và sau đó giảm nó sau khi thêm vào maxSum. Lặp lại quá trình này k lần sẽ cho kết quả.

Để tìm phần tử tối đa của mảng, có thể có nhiều cách và cách hứa hẹn nhất là sử dụng cấu trúc dữ liệu heap tối đa.

Vì vậy, chúng tôi sẽ chèn tất cả các phần tử của mảng vào một đống tối đa, phần tử lớn nhất trong đống được biểu diễn ở gốc của nó. Chúng tôi sẽ xóa nó, thêm vào maxSum và chèn (phần tử -1) trở lại đống. Làm điều này k lần để có được Tối đa mong muốn.

Thuật toán

Khởi tạo - maxSum =0

Bước 1 - Tạo cấu trúc dữ liệu heap tối đa và đẩy các phần tử vào đó.

Bước 2 - Vòng lặp cho i -> 0 đến k và làm theo bộ 3 - 5.

Bước 3 - Lấy phần tử gốc, maxVal =root và bật nó.

Bước 4 - Thêm maxVal vào maxSum, maxSum + =maxVal

Bước 5 - Chèn maxVal đã cập nhật vào đống tối đa.

Bước 6 - Trả về maxSum.

Chương trình minh họa hoạt động của giải pháp của chúng tôi,

Ví dụ

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

Đầu ra

The maximums from array when the maximum decrements after every access is 13