องค์ประกอบสูงสุดที่สามารถทำให้เท่ากับการอัพเดต k ใน C++

ภารกิจคือการค้นหาจำนวนองค์ประกอบสูงสุดที่สามารถทำให้เท่ากันในอาร์เรย์ที่ให้มาหลังจากเพิ่มองค์ประกอบไม่เกิน k ครั้ง

ตอนนี้มาทำความเข้าใจสิ่งที่เราต้องทำโดยใช้ตัวอย่าง -

อินพุต

a[] = {1, 3, 8}, k = 4

ผลลัพธ์

คำอธิบาย

ที่นี่เราสามารถหาสองสี่ได้โดยเพิ่ม 1 สามครั้ง และเพิ่ม 3 สี่ครั้ง นั่นทำให้ a[] ={4, 4, 8}

อินพุต

arr = {2, 5, 9}, k = 2

ผลลัพธ์

แนวทางที่ใช้ในโปรแกรมด้านล่างดังนี้

ในฟังก์ชัน main() เริ่มต้น int a[], ขนาด และ k เพื่อจัดเก็บองค์ประกอบอาร์เรย์ ขนาดของอาร์เรย์ และการอัปเดตสูงสุดตามลำดับ
ในฟังก์ชัน max() ให้เรียงลำดับอาร์เรย์จากน้อยไปมากก่อน แล้วจึงประกาศอาร์เรย์อีกสองอาร์เรย์ int p[size + 1] และ ม.[ขนาด + 1 1] ที่จะเก็บผลรวมคำนำหน้าและค่าสูงสุดตามลำดับ
วนรอบจาก i =0 ถึง i<=size และเริ่มต้น p[i] =0 และ m[i] =0
นอกวงใส่ m[0] =arr[0] และ p[0] =arr[0].
วนจาก i =1 จนถึง i<ขนาดและใส่ p[i] =p[i - 1] + arr[i] เพื่อคำนวณผลรวมคำนำหน้าและใส่ m[i] =max(m[i - 1], arr[i] ) เพื่อคำนวณมูลค่าสูงสุดได้ถึงตำแหน่งนั้น
หลังจากวนรอบแล้ว ให้เริ่มต้น int Lt =1, Rt =size ส่งผลให้เก็บค่าด้านซ้าย ค่าที่ถูกต้อง และคำตอบสุดท้ายตามลำดับ หลังจากนั้นเริ่มการค้นหาแบบไบนารี
เริ่มต้นในขณะที่วนรอบด้วยเงื่อนไข (Lt
อย่างอื่นก็ใส่ Rt =mid -1
นอกผลการพิมพ์แบบวนซ้ำ
ในฟังก์ชัน bool EleCal() เริ่มต้นสำหรับลูปโดยมีเงื่อนไขสำหรับ (int i =0, j =x; j <=size;j++, i++)
ภายในลูปตรวจสอบว่า (x * m[j] - (p[j] - p[i]) <=k) ถ้าเป็นเช่นนั้นแล้วกลับเป็นจริง นอกลูปคืนค่าเท็จ

ตัวอย่าง

#include <bits/stdc++.h>
using namespace std;
bool EleCal(int p[], int m[], int x, int k, int size){
   for (int i = 0, j = x; j <= size; j++, i++){
      if (x * m[j] - (p[j] - p[i]) <= k)
         return true;
   }
   return false;
}
void Max(int arr[], int size, int k){
   // sorting array in ascending order
   sort(arr, arr + size);
   int p[size + 1];
   //array for maximum value
   int m[size + 1];
   // Initialize prefix array and maximum array
   for (int i = 0; i <= size; ++i){
      p[i] = 0;
      m[i] = 0;
   }
   m[0] = arr[0];
   p[0] = arr[0];
   for (int i = 1; i < size; i++){
      // Calculating prefix sum of the array
      p[i] = p[i - 1] + arr[i];
      // Calculating max value upto that position
      // in the array
      m[i] = max(m[i - 1], arr[i]);
   }
   // Binary seach
   int Lt = 1, Rt = size, result;
   while (Lt < Rt){
      int mid = (Lt + Rt) / 2;
      if (EleCal(p, m, mid - 1, k, size)){
         result = mid;
         Lt = mid + 1;
      }
      else
         Rt = mid - 1;
   }
   //answer
   cout<<result;
}
// main function
int main(){
   int a[] = { 1, 3, 8 };
   int size = sizeof(a) / sizeof(a[0]);
   int k = 4;
   Max(a, size, k);
   return 0;
}