警察用C ++捕获小偷

在这个问题中，我们得到了n个元素的数组。数组中的每个元素都有一个警察或一个小偷，一个小偷可以被一个警察抓到，如果警察可以从他那里抓走一个小偷，我们必须找出最大可以被警察抓到的小偷。 。

让我们举个例子来了解这个问题，

输入-

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公里的小偷。

为了解决这个问题，我们将使用贪婪算法。它可以通过两种方式工作，要么抓住距离警察最近的所有小偷，要么抓住距离警察最近的小偷。但是在这两种情况下，都找不到最佳解决方案，因为这两种滞后都是警察必须在距他一定距离的地方抓住小偷的情况。

因此，以下是提供最有希望的结果的算法，

我们将从第一个警察和小偷的索引开始。如果| index(P1)-index(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 << "警察可以逮捕的小偷的最大数量是："<<policeThief(arr2, n, k);
   return 0;
}

输出结果

警察可以逮捕的小偷的最大数量是：4