โปรแกรมหาผลรวมสูงสุดจากการเลือกค่าสูงสุดแล้วลดลง 1 ทีละ k ครั้งใน C++

ให้อาร์เรย์ arr[] และจำนวน m ต้องการเลือกค่าสูงสุด m ครั้ง ทุกครั้งหลังเลือกแล้วลดค่าลง 1 หาผลรวมสูงสุด

ตัวอย่าง: arr=[3,6,7,8,8], k=3 รอบ1: max=8, sum=8, arr=[3,6,7,7,8] รอบ2: max=8, sum=16, arr=[3,6,7,7,7] รอบ3: max=7, sum=23, arr=[3,6,6,7,7] ผลลัพธ์ = 23

วิธีแก้ปัญหา

ใช้ Max Heap (Priority Queue) เก็บทุกค่า ทำ m รอบ: pop ค่าสูงสุด บวกเข้าผลรวม push (ค่า-1) กลับเข้าไป

ตัวอย่างโค้ด C++

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

long calcMaxSumDec(int arr[], int m, int n) {
    long maxSum = 0;
    priority_queue<long> maxHeap;
    for (int i = 0; i < n; i++) maxHeap.push(arr[i]);
    for (int i = 0; i < m; i++) {
        long maxVal = maxHeap.top(); maxHeap.pop();
        maxSum += maxVal;
        maxHeap.push(maxVal - 1);
    }
    return maxSum;
}

int main() {
    int arr[] = {2,3,5,4}, m = 3;
    int n = sizeof(arr)/sizeof(arr[0]);
    cout << calcMaxSumDec(arr, m, n); // 13
    return 0;
}

เอาต์พุต

13