경찰이 C++에서 도둑을 잡는다

이 문제에서는 n 요소의 배열이 제공됩니다. 배열의 각 요소에는 경찰관 또는 도둑이 있으며, 한 명의 경찰이 한 명의 도둑을 잡을 수 있으며 경찰관이 k 단위 떨어진 도둑을 잡을 수 있는 경우 경찰이 잡을 수 있는 최대 도둑 수를 찾아야 합니다.

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

입력 -

array = {T, P, P, P, T , T, T}
K = 2.

출력 - 3

설명 - 여기에서 각 경찰관이 도둑을 잡을 것입니다.

P at index 1 will catch T at index 0.
P at index 2 will catch T at index 4.
P at index 3 will catch T at index 5.

이는 경찰이 2거리에 있는 도둑을 잡을 수 있기 때문에 허용됩니다.

이 문제를 해결하기 위해 greedy 알고리즘을 사용합니다. 그것은 두 가지 방법으로 작동할 수 있습니다. 경찰관에게 가장 가까운 도둑을 모두 잡거나 경찰관에게 가장 멀리 있는 도둑을 잡습니다. 그러나 두 경우 모두 경찰이 일정 거리에서 도둑을 잡아야 하는 경우가 있기 때문에 가장 최적의 솔루션을 찾을 수 없습니다.

따라서 다음은 가장 유망한 결과를 제공하는 알고리즘입니다.

첫 번째 경찰과 도둑의 인덱스부터 시작하겠습니다. |인덱스(P1) - 인덱스(T1)|인 경우 <=k, 도둑은 잡힐 수 있고 우리는 다음 경찰-도둑 쌍을 확인할 것입니다. 그렇지 않으면 min(p,t)을 늘리고 다음 인덱스인 경찰과 도둑을 확인합니다. 이 점검은 모든 경찰과 도둑을 점검하고 마지막에 잡힌 도둑의 수가 인쇄될 때까지 수행됩니다.

예시

우리 알고리즘의 그림을 보여주는 프로그램,

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int policeThief(char arr[], int n, int k){
   int caught = 0;
   vector<int> thieves;
   vector<int> policemen;
   for (int i = 0; i < n; i++) {
      if (arr[i] == 'P')
         policemen.push_back(i);
      else if (arr[i] == 'T')
         thieves.push_back(i);
   }
   int thief = 0, police = 0;
   while (thief < thieves.size() && police < policemen.size()) {
      if (abs(thieves[thief] - policemen[police]) <= k) {
         caught++;
         thief++;
         police++;
      }
      else if (thieves[thief] < policemen[police])
         thief++;
      else
         police++;
   }
   return caught;
}
int main(){
   int k, n;
   char arr2[] = {'P', 'T', 'T', 'P', 'P', 'T', 'T', 'T', 'T', 'P' };
   k = 2;
   n = sizeof(arr2) / sizeof(arr2[0]);
   cout << "Maximum number of thieves that can be caught by police is :"<<policeThief(arr2, n, k);
   return 0;
}

출력

Maximum number of thieves that can be caught by police is :4