Tìm giá trị lớn nhất từ mảng khi giá trị lớn giảm sau mỗi lần truy cập trong C++

Cho mảng arr[] và số nguyên M. Nhiệm vụ: tìm tổng các giá trị lớn nhất khi sau mỗi lần lấy giá trị lớn nhất thì giảm nó đi 1, lặp lại M lần.

Mô tả vấn đề

Tìm phần tử lớn nhất, sau mỗi lần lấy thì giảm nó 1, làm M lần.

Ví dụ:

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

Đầu ra: 17

Giải thích

Lần 1: max = 9, sum = 9, mảng cập nhật = {3, 6, 8, 8}
Lần 2: max = 8, sum = 9+8 = 17, mảng cập nhật = {3, 6, 7, 8}

Phương pháp giải

Dùng max heap (hàng đợi ưu tiên) để phần tử lớn nhất ở gốc. Lấy gốc, giảm 1, chèn lại. Lặp M lần. Mỗi lần lấy gốc, cộng vào tổng và in tổng sau M lần.

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 << "Tổng giá trị lớn nhất khi giảm sau mỗi truy cập: " << getSum(arr, N, M);
}

Đầu ra

Tổng giá trị lớn nhất khi giảm sau mỗi truy cập: 17