Tìm tổng lớn nhất khi lấy phần tử max và giảm nó đi 1 sau mỗi lần trong C++

Mô tả bài toán

Cho mảng arr[] và số m. Thực hiện m lần: lấy phần tử lớn nhất, cộng vào tổng, giảm phần tử đó đi 1. Tìm tổng lớn nhất có được.

Ví dụ: arr = {3,6,7,8,8}, m=3 → 8+8+7=23.

Giải pháp

Dùng max-heap (priority_queue). Lặp m lần: lấy top, cộng vào sum, push (top-1) lại vào heap.

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

long calcMaxSumDec(int arr[], int m, int n) {
    long maxSum = 0;
    priority_queue<long> max_heap;
    for (int i = 0; i < n; i++) max_heap.push(arr[i]);
    for (int i = 0; i < m; i++) {
        long maxVal = max_heap.top(); max_heap.pop();
        maxSum += maxVal;
        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 << "Maximum sum: " << calcMaxSumDec(arr, m, n);
    return 0;
}

Đầu ra

Maximum sum: 13