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

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

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

ในการหาค่าสูงสุด เราจะหาค่าสูงสุดจากอาร์เรย์และหลังจากการดึงข้อมูลทุกครั้งแล้วลดค่าลง -1 Mtimes

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

ป้อนข้อมูล :arr[] ={3, 6, 8, 9} M =2

เอาท์พุต :17

คำอธิบาย

การทำซ้ำครั้งที่ 1 สูงสุด =9 ผลรวม =9 อัปเดต arr ={3, 6, 8, 8}

การทำซ้ำครั้งที่ 2 สูงสุด =8 ผลรวม =9+8 =17 อัปเดต arr ={3, 6, 7, 8}

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

วิธีแก้ไขง่ายๆ คือการใช้ max heap ซึ่งจะมี atroot องค์ประกอบสูงสุด จากนั้นเปิดรูท ลดลง 1 แล้วใส่องค์ประกอบอีกครั้ง นี่คือป๊อปและแทรกเสร็จสิ้น M ครั้ง สำหรับการดำเนินการป๊อปแต่ละครั้ง เราจะเพิ่มองค์ประกอบให้กับองค์ประกอบผลรวมและพิมพ์ผลรวมหลังการทำซ้ำ 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