การหาค่าสูงสุดจากอาร์เรย์เมื่อค่าสูงสุดลดลงหลังการเข้าถึงแต่ละครั้งใน C++

ในปัญหานี้ เราได้รับอาร์เรย์ arr[] และจำนวนเต็ม M ภารกิจของเราคือการสร้างโปรแกรมเพื่อหาค่าสูงสุดจากอาร์เรย์เมื่อค่าสูงสุดลดลงหลังการเข้าถึงแต่ละครั้งใน C++

คำอธิบายปัญหา

เพื่อหาค่าสูงสุด เราจะหาสมาชิกที่มีค่าสูงสุดจากอาร์เรย์ และหลังจากดึงค่าออกมาแต่ละครั้ง จะลดค่าลง 1 ทำซ้ำ M ครั้ง

ตัวอย่างเพื่อเข้าใจปัญหา:

อินพุต: arr[] = {3, 6, 8, 9}, M = 2

เอาต์พุต: 17

คำอธิบาย

รอบที่ 1: ค่าสูงสุด = 9, ผลรวม = 9, อาร์เรย์อัปเดต = {3, 6, 8, 8}

รอบที่ 2: ค่าสูงสุด = 8, ผลรวม = 9+8 = 17, อาร์เรย์อัปเดต = {3, 6, 7, 8}

แนวทางแก้ปัญหา

วิธีแก้ที่เรียบง่ายคือใช้ max heap ซึ่งจะมีค่าสูงสุดอยู่ที่ราก (root) จากนั้นนำรากออก (pop) ลดค่าลง 1 แล้วนำกลับเข้า heap (insert) อีกครั้ง การ pop และ insert นี้ทำซ้ำ M ครั้ง สำหรับแต่ละครั้งที่ pop เราจะบวกค่าที่ได้เข้ากับผลรวม และพิมพ์ผลรวมหลัง M รอบ

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

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

ผลลัพธ์

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