ในปัญหานี้ เราได้รับอาร์เรย์ arr[] ของจำนวนเต็ม N และจำนวนเต็ม m งานของเราคือสร้างโปรแกรมเพื่อค้นหาค่าสูงสุดจากอาร์เรย์เมื่อค่าสูงสุดลดลงหลังจากการเข้าถึงทุกครั้ง
คำอธิบายปัญหา − เราจำเป็นต้องหาผลรวมสูงสุดขององค์ประกอบสูงสุดของอาร์เรย์และลดค่าสูงสุดที่ได้มาหนึ่ง k เท่า
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
อินพุต
arr[] = {3, 6, 7, 8, 8}, k = 3 ผลลัพธ์
คำอธิบาย
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 แนวทางการแก้ปัญหา
แนวคิดคือการหาค่าสูงสุดของอาร์เรย์แล้วลดลงหลังจากเพิ่มใน maxSum การทำซ้ำขั้นตอนนี้ k ครั้งจะให้ผลลัพธ์
สำหรับการค้นหาองค์ประกอบสูงสุดของอาร์เรย์ สามารถทำได้หลายวิธี และวิธีที่เป็นไปได้มากที่สุดคือการใช้โครงสร้างข้อมูลฮีปสูงสุด
ดังนั้น เราจะแทรกองค์ประกอบทั้งหมดของอาร์เรย์ลงในฮีปสูงสุด องค์ประกอบสูงสุดในฮีปจะแสดงที่รูทของมัน เราจะลบมัน เพิ่มใน maxSum และแทรก (องค์ประกอบ -1) กลับไปที่ฮีป ทำ k ครั้งเพื่อรับ maxSum ที่ต้องการ
อัลกอริทึม
เริ่มต้น − maxSum =0
ขั้นตอนที่ 1 − สร้างโครงสร้างข้อมูลฮีปสูงสุดและผลักองค์ประกอบเข้าไป
ขั้นตอนที่ 2 − วนรอบสำหรับ i -> 0 ถึง k และติดตามชุดที่ 3 - 5
ขั้นตอนที่ 3 − นำองค์ประกอบรูท maxVal =root แล้วป๊อปอัป
ขั้นตอนที่ 4 − เพิ่ม maxVal ให้กับ maxSum, maxSum +=maxVal
ขั้นตอนที่ 5 − แทรก maxVal ที่อัปเดตไปยังฮีปสูงสุด
ขั้นตอนที่ 6 − ส่งคืนผลรวมสูงสุด
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
ตัวอย่าง
#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);
} ผลลัพธ์
The maximums from array when the maximum decrements after every access is 13
