C++에서 최소 거리가 최대화되도록 배열에서 점 선택

이 문제에서 N개의 인덱스 위치를 나타내는 n개의 요소로 구성된 배열 arr[]이 주어지고 C개의 자석이 있습니다. 우리의 임무는 가장 가까운 두 자석 사이의 거리가 가능한 한 크게 되도록 이 모든 자석을 인쇄하는 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력 - 배열 ={ 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