এই সমস্যাতে, 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.
এটি অনুমোদিত কারণ পুলিশ তার থেকে দূরত্ব ২-এ থাকা চোরকে ধরে পাকতে পারে।
সমাধানের জন্য, আমরা লালচী অ্যালগরিদম (greedy algorithm) ব্যবহার করব। এটি দুভাবে কাজ করতে পারে: либо পুলিশের নিকটতম চোর ধরে অথবা দূরতম চোর। কিন্তু দুটি কেসেই সর্বোত্তম সমাধান নাও পাওয়া যায় কারণ কিছু কেসে পুলিশকে নির্দিষ্ট দূরত্বের চোর ধরতে হয়।
সর্বোত্তম ফলাফল দেয় এমন একটি অ্যালগরিদম:
আমরা প্রথম পুলিশ এবং চোরের ইনডেক্স থেকে শুরু করব। যদি |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 thieves;
vector 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
