Cảnh sát bắt kẻ trộm trong C ++

Trong bài toán này, chúng ta được đưa ra một mảng gồm n phần tử. Mỗi phần tử của mảng có một cảnh sát hoặc một tên trộm, một tên trộm có thể bị một cảnh sát bắt và chúng ta phải tìm số kẻ trộm tối đa có thể bị cảnh sát bắt nếu một cảnh sát có thể bắt kẻ trộm cách xa anh ta k đơn vị.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào -

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

Đầu ra - 3

Giải thích - ở đây, mỗi cảnh sát sẽ bắt một tên trộm,

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.

Điều này được cho phép vì cảnh sát có thể bắt được những tên trộm ở cách chúng 2 khoảng cách.

Để giải quyết vấn đề này, chúng ta sẽ sử dụng thuật toán tham lam. Nó có thể hoạt động theo hai cách, hoặc bắt tất cả những tên trộm gần cảnh sát nhất hoặc bắt những tên trộm xa nhất với cảnh sát. Nhưng trong cả hai trường hợp, giải pháp tối ưu nhất không được tìm thấy vì cả hai đều chậm trễ là một số trường hợp cảnh sát phải bắt một tên trộm ở một khoảng cách nhất định từ hắn ta.

Vì vậy, sau đây là một thuật toán cung cấp kết quả hứa hẹn nhất,

Chúng ta sẽ bắt đầu với các chỉ số của cảnh sát đầu tiên và tên trộm. Nếu | index (P1) - index (T1) | <=k, kẻ trộm có thể bị bắt và chúng tôi sẽ kiểm tra cặp cảnh sát - tên trộm tiếp theo. Nếu không, chúng tôi sẽ tăng min (p, t) và kiểm tra chỉ số tiếp theo của cảnh sát và tên trộm. Việc kiểm tra này sẽ được thực hiện cho đến khi tất cả cảnh sát và kẻ trộm được kiểm tra và cuối cùng thì số tên trộm bị bắt được in ra.

Ví dụ

Chương trình hiển thị hình minh họa thuật toán của chúng tôi,

#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;
}

Đầu ra

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