เลือกจุดจากอาร์เรย์เพื่อให้ระยะทางต่ำสุดขยายใหญ่สุดใน C++

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

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

ป้อนข้อมูล − array ={ 1, 4, 6,12, 28, 44 } C =4

ผลผลิต − 11

เพื่อแก้ปัญหานี้ เราจะใช้การค้นหาแบบไบนารีในระยะทางสูงสุด เราจะกำหนดระยะสูงสุดแล้ววางแม่เหล็กทั้งหมดระหว่าง 0 ถึงระยะทางสูงสุดได้

จากนั้นเราจะใช้การค้นหาแบบไบนารีเพื่อค้นหาค่าตรงกลางและตรวจสอบว่าสามารถวางแม่เหล็กได้หรือไม่ ถ้าใช่ ให้วางแม่เหล็กและถือว่าระยะกลางเป็นระยะห่างสูงสุด แล้วทำตามขั้นตอนเดียวกัน

ตัวอย่าง

โปรแกรมแสดงการใช้งานโซลูชันของเรา

#include <iostream>
using namespace std;
bool canPlace(int arr[], int n, int C, int mid){
   int magnet = 1, currPosition = arr[0];
   for (int i = 1; i < n; i++) {
      if (arr[i] - currPosition >= mid) {
         magnet++;
         currPosition = arr[i];
         if (magnet == C)
            return true;
      }
   }
   return false;
}
int minDistMax(int n, int C, int arr[]){
   int lo, hi, mid, ans;
   lo = 0;
   hi = arr[n - 1];
   ans = 0;
   while (lo <= hi) {
      mid = (lo + hi) / 2;
      if (!canPlace(arr, n, C, mid))
         hi = mid - 1;
      else {
         ans = max(ans, mid);
         lo = mid + 1;
      }
   }
   return ans;
}
int main(){
   int C = 4;
   int arr[] = { 1, 4, 6,12, 28, 44 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout<<"Maximised Minimum distance is "<<minDistMax(n, C, arr);
   return 0;
}

ผลลัพธ์

Maximised Minimum distance is 11